笨人小白的温故知新——排序（2）

这是一个一题多解的博客！下面是一道很简单的题：

1177：奇数单增序列

题目描述】

【输入】

【输出】

【输入样例】

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循环执行后：

1. 左指针i：最终停在第一个不小于基准值x的元素上（即q[i] ≥ x，之前跳过的所有元素都是q[?] < x）；
2. 右指针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 ; }

明天我将用其他几种方法来做一下这道题！