排序在程序设计中是非常重要的,排序的种类很多,我在这里只列举了几种简单好用的排序。
冒泡排序
核心思想是贪心,这个算法应该是最经典的排序算法了,我第一次接触到的排序算法就是这个,当年学的时候还困扰了我好久。。其实挺简单的。
核心思想是:我们每次将相邻的元素进行比较,如果存在逆序\(i<j \,\,\&\& a\left[ i \right] > a\left[ j \right]\)就进行交换,第一趟完成之后,最大的元素就位,第\(n\)趟之后,第 \(n\) 大的元素就位。
代码:
#include<iostream> using namespace std; int arr[100]; void swap(int & a, int & b) { int t = a; a = b; b = t; } void bubble_sort(int len) { for(int i = len - 1 ; i >= 0 ; --i) { for(int j = 0 ; j < i ; ++j) { if(arr[j] > arr[j+1]) { //相邻比较 swap(arr[j] , arr[j+1]); } } } } int main() { for(int i = 0 ; i <= 10 ; ++i) { arr[i] = 10 - i; } bubble_sort(10); for(int i = 0 ; i < 10 ; ++i) cout << arr[i] << endl; return 0; }
选择排序
核心思想是减治,将序列分为左右两个部分,左边部分为乱序,右边部分为有序,每次将左边序列中的最大值与右边序列的前一个元素进行交换,反复迭代之后,左边序列为空,右边序列即为整个序列。

代码:
#include<iostream> using namespace std; int arr[100]; void swap(int & a , int & b) { int t = a; a = b; b = t; } void selection_sort(int len) { int t; for(int i = len ; i >= 0 ; --i) { int t = i; //将最后一个设置为最大元素 for(int j = 0 ; j < i ; ++j) { //在前面寻找最大元素 if(arr[j] > arr[t]) { t = j; } } if(t != i) { swap(arr[t], arr[i]); } } } int main() { for(int i = 0 ; i < 10 ; i++) { arr[i] = 10 - i; } selection_sort(10); for(int i = 0 ; i < 10 ; ++i) { cout << arr[i] << endl; } }
堆排序
在讲优先级队列的时候说过,使用堆这种数据结构,可以仅用\(O\left( \log n \right) \)的时间就可以得到最大或最小的元素,所以我们可以使用堆来维护无序的部分,每次取出最大的元素插入到有序部分。(这里我为了简单没有建堆。。而是直接用的priority_queue,c语言里面没有这种东西还是得自己写)
#include<iostream> #include<queue> using namespace std; int arr[100]; void heap_sort(int len) { priority_queue<int> PQ; for(int i = 0 ; i < len ; ++i) { PQ.push(arr[i]); } for(int i = len - 1 ; i >= 0 ; --i) { arr[i] = PQ.top(); PQ.pop(); } } int main() { for(int i = 0 ; i < 10 ; ++i) { arr[i] = 10 - i; } heap_sort(10); for(int i = 0 ; i < 10 ; ++i) { cout << arr[i] << endl; } }
插入排序
插入排序也是基于减而治之的思想,左边序列为有序部分,右边序列为无序部分,我们每次取出右边的第一个元素,插入到左边序列中,使其仍然有序。一般我们认为,插入排序虽然时间复杂度和选择排序一样均为\(O\left( n^2 \right) \),但插入排序的好处是我们可以对数据进行在线处理,我们不必每次都需要一个完整的序列,而是来一个数据,我们处理一个数据,这种支持在线处理的算法是非常重要的。

代码:
#include<iostream> #include<stdlib.h> using namespace std; int arr[100]; void insertion_sort(int len) { for(int i = 1; i < len ; ++i) { int tmp = arr[i]; //插入的值 for(int j = 0 ; j < i ; ++j) { //从有序的地方开始找 if(tmp < arr[j]) { //找到插入的地方 for(int k = i; k > j ; --k) { //挪动元素开始插入 arr[k] = arr[k - 1]; } arr[j] = tmp; //找到合适的位置了,进行插入 break; } } } } int main() { for(int i = 0 ; i < 20 ; ++i) arr[i] = rand() % 100 + 1; cout << "原始" << endl; for(int i = 0 ; i < 20 ; ++i) cout << arr[i] << endl; insertion_sort(20); cout << "插入" << endl; for(int i = 0 ; i < 20 ; ++i) cout << arr[i] << endl; return 0; }
PS: 插入排序的代码一不小心就会写错。。一定要细心。。
归并排序
和前面的几种排序算法的核心思想有略微的区别,归并排序的核心思想时分治,将一个大问题分解为若干个小问题,然后同时处理(一般用递归实现)。如果我们需要对一个序列进行排序,我们只需要对其左边部分进行排序,再对右边部分进行排序,排序完成后,我们将其合并就完成了。如果我们需要对其左边部分进行排序,我们只需要将左边序列的左边序列进行排序......然后就递归下去了,直到问题被转化成每一个序列都是一个单独的元素,那我们就相当于排好序了:

我们只需要再进行归并就好了,我们使用二路归并来进行处理:

当我们需要合并两个有序序列的时候,我们只需要比较它们中的首元素,谁小就将其放入一个新的序列中,这个思路应该不难理解,代码实现会有一点点麻烦。

代码:
#include<iostream> using namespace std; int arr[10005]; int b[10005]; void mergesort(int L, int R) { if(L == R) return; int mid = (L + R) >> 1; //相当于除以2,找到中点位置 mergesort(L, mid); //左边进行排序 mergesort(mid + 1, R); //右边进行排序 int Ldx = L; int Rdx = mid + 1; int New_dx = L; while(Ldx <= mid && Rdx <= R) { //进行归并,谁小就将谁加入新的序列中 if(arr[Ldx] < arr[Rdx]) { b[New_dx++] = arr[Ldx++]; } else { b[New_dx++] = arr[Rdx++]; } } while(Ldx <= mid) { //上一轮循环如果没有加完,就将数据全部存入新序列 b[New_dx++] = arr[Ldx++]; } while(Rdx <= R) { b[New_dx++] = arr[Rdx++]; } for(int i = L ; i <= R ; ++i) { //最后将新序列还原到原序列中 arr[i] = b[i]; } } int main() { for(int i = 0 ; i < 10 ; ++i) { arr[i] = 10 - i; } mergesort(0, 9); //左右都是闭区间 for(int i = 0 ; i < 10 ; ++i) { cout << arr[i] << endl; } }
时间复杂度为\(O\left( n\log n \right) \)
快速排序
快速排序应该是用的最多的一种排序了,STL库中的sort函数就是快速排序,快速排序的思想是:我们每次都选定一个界限,根据这个界限,我们将序列调整为左边的元素都比他小,右边的元素都比他大:

调整完成后,我们再对左右两边的序列进行同样的处理,直到序列有序。关于界限的选定,我是随机取的,应该有更好的办法,但是很麻烦。。
代码:
#include<iostream> #include<stdlib.h> using namespace std; int arr[10005]; void swap(int & a, int & b) { int t = a; a = b; b = t; } void quicksort(int L, int R) { if(L > R) return; int Ldx = L; int Rdx = R; int bound = arr[rand() % (R - L + 1) + L]; //在L和R之间,随机选择一个值作为界桩 while(Ldx <= Rdx) { while(arr[Ldx] < bound) { //这一轮循环迭代完后,ldx指向的是大于或等于界桩的数,需要被安排一下 Ldx ++; } while(arr[Rdx] > bound) { //这一轮循环迭代完后,rdx指向的是小于或等于界桩的数,也需要被安排一下 Rdx --; //因为我们要保证左边的数都比界桩要小,右边的数都比界桩要大。 } if(Ldx <= Rdx) { //如果是在范围内,我们将其进行调换。 swap(arr[Ldx++], arr[Rdx--]); } } //大循环迭代完后,Rdx会指向mid左边一个,ldx会指向mid右边的一个,不信你可以验证一下 quicksort(L, Rdx); //然后我们在对左边的数据进行处理 quicksort(Ldx, R); //对右边的数据进行处理 } int main () { for(int i = 0 ; i < 10 ; ++i) { arr[i] = 10 - i; } quicksort(0, 9); for(int i = 0 ; i < 10 ; ++i){ cout << arr[i] << endl; } return 0; }
如果你问我在刷题的时候我会用什么排序,我一定会说std::sort真香😄。不过把排序算法都自己尝试实现一遍,会对这些算法思想有更深刻的认识哦。
Comments | NOTHING