这是一个一题多解的博客！下面是一道很简单的题：
1177：奇数单增序列
题目描述】
给定一个长度为N（不大于500）的正整数序列，请将其中的所有奇数取出，并按升序输出。
【输入】
第1行为 N；
第2行为 N 个正整数，其间用空格间隔。
【输出】
增序输出的奇数序列，数据之间以逗号间隔。数据保证至少有一个奇数。
【输入样例】
10 1 3 2 6 5 4 9 8 7 10【输出样例】
1,3,5,7,9方法一：插入法
void insertSort(int a[], int n) { for(int i = 1 ; i < n ; i ++){ if(a[i] < a[i-1]){ int j = i-1 ; int x = a[i] ; while(j >= 0 && a[j] > x){ a[j+1] = a[j] ; j -- ; } a[j+1] = x ; } } }这就是插入法的代码模板。它的原理很简单，就是以一个乱序的数组中的第一个数为基石，通过后面的数与前面的数字比较，将数字逐一为它们找到自己的位置。
下面是插入法写出来的AC代码：
#include <iostream> #include <stdio.h> using namespace std ; void insertSort(int a[], int n) { for(int i = 1 ; i < n ; i ++){ if(a[i] < a[i-1]){ int j = i-1 ; int x = a[i] ; while(j >= 0 && a[j] > x){ a[j+1] = a[j] ; j -- ; } a[j+1] = x ; } } } int main(){ int n , a[505] , k = 0 ; cin >> n ; for(int i = 0 ; i < n ; i ++) scanf("%d" , &a[i]) ; insertSort(a , n) ; int first = 1 ; for(int i = 0 ; i < n ; i ++){ if(a[i] % 2 == 1){ if(first == 1){ first = 0 ; printf("%d", a[i]) ; continue ; } else if(first == 0) printf(",%d" , a[i]) ; } } return 0 ; }方法二：归并排序
#include <iostream> #include <algorithm> using namespace std ; const int N = 1e6+10 ; int tmp[N] ; void mergesort(int q[] , int l , int r){ if(l >= r) return ; int mid = l + r >> 1 ; mergesort(q , l , mid) ; mergesort(q , mid+1 , r) ; int i = l , j = mid+1 , k = 0 ; while(i <= mid && j <= r){ if(q[i] <= q[j]) tmp[k++] = q[i++] ; else tmp[k++] = q[j++] ; } while(i <= mid) tmp[k++] = q[i ++] ; while(j <= r) tmp[k++] = q[j ++] ; for(i = l , j = 0 ; i <= r ; i ++ , j ++) q[i] = tmp [j] ; } int main(){ int n , len , k = 0 ; cin >> n ; len = n ; int* a = new int[n] ; while(n --) scanf("%d" , &a[k++]) ; mergesort(a , 0 , len-1) ; int first = 1 ; for(int i = 0 ; i < len ; i ++){ if(a[i] % 2 == 1){ if(first == 1){ first = 0 ; printf("%d", a[i]) ; continue ; } else printf(",%d" , a[i]) ; } } return 0 ; }这里，我用了动态数组来优化！
方法三：快速排序
在
do-while循环执行后：
- 左指针
i：最终停在第一个不小于基准值x的元素上（即q[i] ≥ x，之前跳过的所有元素都是q[?] < x）；- 右指针
j：最终停在第一个不大于基准值x的元素上（即q[j] ≤ x，之前跳过的所有元素都是q[?] > x）；简单说：
i指向了左区间里「不该出现的大元素」，j指向了右区间里「不该出现的小元素」。
以上是我的困惑点，这是豆包为我作的解答。以下是我的AC代码：
#include <iostream> #include <algorithm> using namespace std ; const int N = 505 ; void quick_sort(int q[] , int l , int r){ if(l >= r) return ; int i = l-1 , j = r+1 , x = q[l+r>>1] ; while(i < j){ do i ++ ; while(q[i] < x) ; do j -- ; while(q[j] > x) ; if(i < j) swap(q[i] , q[j]) ; } quick_sort(q , l , j) , quick_sort(q , j+1 , r) ; } int main(){ int n , len , k = 0 , a[N]; cin >> n ; len = n ; while(n --) scanf("%d" , &a[k++]) ; quick_sort(a , 0 , len-1) ; int first = 1 ; for(int i = 0 ; i < len ; i ++){ if(a[i] % 2 == 1){ if(first == 1){ first = 0 ; printf("%d", a[i]) ; continue ; } else printf(",%d" , a[i]) ; } } return 0 ; }明天我将用其他几种方法来做一下这道题！
)