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

我来啦！今天依旧是1177：奇数单增序列的一题多解。

（不厌其烦地附上题目）

【题目描述】

【输入】

【输出】

【输入样例】

10 1 3 2 6 5 4 9 8 7 10

【输出样例】

1,3,5,7,9

方法四：冒泡排序

我在大佬源代码的基础上，将q[j]与q[j+1]的复制与赋值换成了swap（）函数！嘻嘻，我会a little bit举一反三了！

这个flag是用来判断当前数组是否已经有序的，其实没有flag也不影响理解哒！

#include <iostream> #include <algorithm> using namespace std ; void bubblesort(int q[] , int n){ for(int i = 0 ; i < n - 1 ; i ++){ bool flag = true ; //用一个flag来判断当前数组是否已经有序，有序则推退出循环 for(int j = 0 ; j < n - 1 ; j ++){ if(q[j] > q[j+1]){ swap(q[j] , q[j+1]) ; flag = false ; } } if(flag) break ; } } int main(){ int n , len , k = 0 ; cin >> n ; len = n ; int* a = new int[n] ; while(n --) scanf("%d" , &a[k++]) ; bubblesort(a , len) ; 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 ; }

方法五：希尔排序

看了希尔排序的动画后，就觉得这玩意儿 和插入排序怎么那么像，看到它的模板代码后发现，这俩真的超级像！

希尔排序比插入排序多的一个地方是增量gap。希尔排序每次都选择gap/2作为它的步长（初始的gap为n/2），根据这个步长分组进行排序，使得每次排序的工作量都比较小。

#include <iostream> #include <algorithm> using namespace std ; void shellsort(int q[] , int n){ for(int gap = n/2 ; gap >= 1 ; gap/=2){ for(int i = gap ; i < n ; i += gap){ int temp = q[i] ; int pre = i - gap ; while(pre >= 0 && q[pre] > temp){ q[pre+gap] = q[pre]; pre -= gap ; } q[pre + gap] = temp ; } } } int main(){ int n , len , k = 0 ; cin >> n ; len = n ; int* a = new int[n] ; while(n --) scanf("%d" , &a[k++]) ; shellsort(a , len) ; 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 ; }

方法五：选择排序

#include <iostream> #include <algorithm> using namespace std ; void selectionsort(int q[] , int n){ for(int i = 0 ; i < n ; i ++){ int min = i ; for(int j = i+1 ; j < n ; j ++){ if(q[j] < q[min]) min = j ; } int temp = q[min] ; q[min] = q[i] ; q[i] = temp ; } } int main(){ int n , len , k = 0 ; cin >> n ; len = n ; int* a = new int[n] ; while(n --) scanf("%d" , &a[k++]) ; selectionsort(a , len) ; 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 ; }