这里写目录标题

前言冒泡排序选择排序插入排序归并排序快速排序

前言

之前笔试遇到了很多排序的题，问第一轮排序后的结果，每次都有点蒙。于是决定手撕一下各种排序算法，包含冒泡排序，选择排序，插入排序，归并排序，快速排序

全局变量和代码块如下

int a[10] = {69, 70, 21, 26, 18, 21, 94, 43, 4, 37}; const int N = 10; void show() { for(int i = 0; i < N; i++) cout << a[i] << " "; cout << endl; }

冒泡排序

原理： 将大的数沉下去，小的数慢慢浮上来。比较相邻的两个数，第i次排序将第i大的数放到倒数第i位。

//冒泡排序 /* 将大的数沉下去，小的数慢慢浮上来 比较相邻的两个数 第i次排序将第i大的数放到倒数第i位 */ void Bubble_sort() { for(int i = 0; i < N; i++){//每次下层第i个数 for(int j = 0; j < N-i-1; j++){ if(a[j] > a[j+1]) swap(a[j], a[j+1]);//交换 } cout << "冒泡排序每一轮结果" << endl; show(); } }

每轮排序之后的结果如下

选择排序

每次找到第i小的数放到位置i上，从第i+1开始找，得到最小值的下标

//选择排序 /* 从头至尾扫描序列，找出最小的一个元素 和第一个元素交换 接着从剩下的元素中继续这个操作 */ void Select_sort() { for(int i = 0; i < N; i++){ int idx = i;//带寻找到的下标 for(int j = i+1; j < N; j++){ if(a[j] < a[idx]) idx = j; } swap(a[i], a[idx]); cout << "选择排序每一轮的结果" << endl; show(); } }

插入排序

插入排序是将前面的序列看成已经排好序的，将后面的数字插入到对应的位置。比如23 45 78 30 25，排到30的时候，把30放到23和45中间就行。这里有两步操作，找到位置然后后移

//插入排序 /* 将待排序的数看成一个有序序列 每次取当前的数插入到合适的位置 从第二个数开始 */ void Insert_sort() { for(int i = 1; i < N; i++){ int pos = i-1;//最后一个有序的位置 int cur = a[i]; while(pos >= 0 && cur < a[pos]){ a[pos+1] = a[pos]; pos--;//找到合适的位置 } a[pos+1] = cur; cout << "插入排序每轮的排序结果" << endl; show(); } }

归并排序

归并排序相比之前的排序要稍微复杂一点。归并排序的思想是将数组2分成一段一段的数组，然后将分段的数组分别排序，然后在合并成有序的数组

//因为会分成长度为2的小数组 //所以可以认定t1,t2是有序的 void Merge(int L, int mid, int R) { int n1 = mid-L+1;//左边数组的长度 int n2 = R-mid; vector<int> t1, t2; for(int i = 0; i < n1; i++) t1.push_back(a[L+i]); for(int i = 0; i < n2; i++) t2.push_back(a[mid+i+1]); int k = L;//开始重新装到原数组里面 int i = 0, j = 0;//i, j对应t1, t2的下标 while(k <= R){ if(i < n1 && j < n2){ if(t1[i] < t2[j]){ a[k] = t1[i]; i++; } else{ a[k] = t2[j]; j++; } k++; } else{ while(i < n1 && k <= R){ a[k] = t1[i]; i++; k++; } while(j < n2 && k <= R){ a[k] = t2[j]; j++; k++; } } } } //归并排序 /* 将排序的数组分治划分为小的数组 对小的数组排序 合并成大的数组 */ void Merge_sort(int L, int R) { if(L < R){ int mid = (L+R)/2; Merge_sort(L, mid); Merge_sort(mid+1, R); Merge(L,mid, R); show(); } }

从运行过程可以看得出来是先划分成小块，然后对小块排序，在合成有序的大块

快速排序

快速排序也可以说是利用的分治的思想，但是快排是选定一个目标值，将数组分为有序两个部分，即左边的比目标值小，右边的比目标值大。但是左右两边的数组又是无序的，只要将两边的数组有序，即完成排序

void quick_sort(int L, int R) { if(L < R){ //找到分割的下标 int i = L, j = R; int x = a[i];//比x小的都放到左边，大的都放到右边去 while(i < j){ //从右往左找第一个小于x的数 while(i < j && a[j] > x) j--; if(i < j) a[i++] = a[j]; //从左往右找到第一个大于x的数 while(i < j && a[i] < x) i++; if(i < j) a[j--] = a[i]; } a[i] = x; show(); quick_sort(L, i-1); quick_sort(i+1, R); } }

具体来说就是选定第一个值作为目标值，然后从右往左找到第一个小于它的，交换位置。然后从左往右找第一个大于它的交换位置。左右交接处就是目标值的位置，这就是一次快速排序。