各种排序算法代码实现（插入，希尔，选择，快速，冒泡，堆排序，基数排序）

#include<iostream> #include<vector> using namespace std; vector<int> m_Insert1(vector<int > vi, int n) { vector<int > res; if (n <= 1)return vi; res.push_back(vi[0]); for(int i=1; i<n; i++) { int m = res.size(); if (vi[i] <= res[0]) { res.insert(res.begin(), vi[i]); continue; } if (vi[i] >= res[m - 1]) { res.insert(res.end(), vi[i]); continue; } for (int j = 0; j < n-1; j++) { if (vi[i] >= res[j] && vi[i] <= res[j + 1]) { res.insert(res.begin() + j + 1, vi[i]); break; } } } return res; } vector<int> m_Insert2(vector<int > vi, int n) { if (n <= 1)return vi; for (int i = 1; i < (int)vi.size(); i++) { //如果，第i个元素(vi[i]=temp) 小于 第i-1个元素，则将i前面的 大于 temp的逐个后移（按顺序）， //直到遇到小于等于temp的元素为止。如 5 7 3 8 1 4 ----->3 5 7 8 1 4--->1 3 5 7 8 4--->1 3 4 5 7 8 //稳定的 if (vi[i] < vi[i - 1]) { int temp = vi[i]; int k = i-1; while (k >= 0 && vi[k] > temp) { vi[k+1] = vi[k]; k--; } vi[k + 1] = temp; } } return vi; } vector<int> m_shellSort(vector<int > vi, int n) { if (n <= 1)return vi; //不稳定 //取数间隔gap。每隔gap取一个数，形成gap个数组（虚拟的，依然在原数组上进行操作），分别对其进行插入排序 for (int gap = n / 2; gap >= 1; gap /= 2) { for (int i = 0; i < gap; i++) { //插入排序 for (int j = i + gap; j < n; j += gap) { if (vi[j] < vi[j - gap]) { int k = j - gap; int temp = vi[j]; while (k >= 0 && vi[k] > temp) { vi[k + gap] = vi[k]; k -= gap; } vi[k + gap] = temp; } } } } return vi; } //稳定 vector<int> m_bobbleSort1(vector<int > vi, int n) { if (n <= 1)return vi; for(int i=0; i<n-1; i++) for (int j = 0; j < n-1; j++) { if (vi[j] > vi[j + 1]) { int temp = vi[j]; vi[j] = vi[j + 1]; vi[j + 1] = temp; } } return vi; } vector<int> m_bobbleSort2(vector<int > vi, int n) { if (n <= 1)return vi; int cnt = 0;//每次遍历交换次数，若某次为0，则排序完成 for (int i = 0; i < n - 1; i++) { cnt = 0; for (int j = 0; j < n - 1; j++) { if (vi[j] > vi[j + 1]) { int temp = vi[j]; vi[j] = vi[j + 1]; vi[j + 1] = temp; cnt++; } } if (cnt == 0)break; } return vi; } vector<int> m_bobbleSort3(vector<int > vi, int n) { if (n <= 1)return vi; int sit = 0;//记录每次遍历时最后一次数据交换的位置，后面未交换的代表已经有序了，不需在考虑 for (int i = 0; i < n - 1; i++){ sit = 0; for (int j = 0; j < n - 1; j++) { if (vi[j] > vi[j + 1]) { int temp = vi[j]; vi[j] = vi[j + 1]; vi[j + 1] = temp; sit = j; } } if (sit == 0)break; } return vi; } //不稳定 //递归调用，双指针形式，一个左一个右，随机选基准，从右开始，（递减）若右指针指向的值 小于 基准，则赋给左指针指向的变量（从基准位开始）， //在移动左指针（递增）若左指针指向的值 大于 基准，则赋给右指针指向的变量 //交替，直到 left >= right void m_quickSort(vector<int > &vi, int start, int end) { if (start < end) { int base = vi[start]; int left = start, right = end; while (left < right) { while (vi[right] >= base && left < right)right--; if (left < right) vi[left] = vi[right]; while (vi[left] <= base && left < right)left++; if (left < right) vi[right] = vi[left]; } vi[left] = base; m_quickSort(vi, start, left - 1); m_quickSort(vi, left + 1, end); } } //不稳定 //依次遍历，每次选择无序数组中最小值和起点交换值。遍历起点从有序数组末尾开始。 //如3 6 7 4 8 1 5(从0开始)---->1 6 7 4 8 3 5(从1开始)---->1 3 7 4 8 6 5(从2开始)--->1 3 4 7 8 6 5--->1 3 4 5 8 6 7--->1 3 4 5 6 8 7--->1 3 4 5 6 7 8 vector<int> m_selectSort(vector<int > vi, int n) { if (n <= 1)return vi; for (int i = 0; i < n; i++) { int mask = i; for (int j = i ; j < n; j++) { if (vi[j] < vi[mask]) mask = j; } swap(vi[i], vi[mask]); } return vi; } //堆排序 （最大堆） 不稳定 //挺像选择排序，但选择最值的方式不同 //https://blog.csdn.net/morewindows/article/details/6709644 void m_heapSort(vector<int > &vi, int end) { if (end <= 1)return; //（满二叉）叶子节点，没有子节点。默认其符合最大堆的要求。共 n 个节点，则非叶子节点有 n/2（不含0，程序中是从0开始计数） //因此，只需要调整各非叶子节点（子树的根节点）的子树。将子节点中最大的值并且 大于 根节点值的节点与子树的根节点交换。 //最后，找到了一个最大值。让其与数组最后一位交换。 for (int i = (end-1) / 2 - 1; i >= 0; i--) {//不是叶子节点的节点数 = i， int k = i; int temp = vi[k]; int j = 2 * k + 1; while (j<end) { if (j + 1 < end && vi[j + 1] > vi[j]) j++; if (vi[j] < temp) break; vi[k] = vi[j]; k = j; j = 2 * k + 1; } vi[k] = temp; } swap(vi[0], vi[end - 1]); m_heapSort(vi, end - 1); } //两个有序数列，合并排序，可用优先队列实现。 void merge(vector<int >& vi, int first, int mid, int last) { int n = last - first + 1; int* p = new int[n]; memset(p, 0, n); int i = first, j = mid + 1; int k = 0; while (i <= mid && j <= last) { if (vi[i] <= vi[j]) p[k++] = vi[i++]; else p[k++] = vi[j++]; } while(i<=mid) p[k++] = vi[i++]; while(j<=last) p[k++] = vi[j++]; for (int l = 0; l < n; l++) vi[first + l] = p[l]; delete[] p; } //递归产生两有序子数列， void memetySort(vector<int >& vi, int first, int last) {//last指向最后一个元素，last = n-1 if (first < last) { int mid = (first + last) / 2; memetySort(vi, first, mid); memetySort(vi, mid+1, last); merge(vi, first, mid, last); } } //基数排序 //https://www.runoob.com/w3cnote/radix-sort.html 看动图 int max_cnt(vector<int> vi, int n) {//求最大值是几位数 int m = vi[0]; int cnt = 1; for (int i = 1; i < n; i++) { if (m < vi[i])m = vi[i]; } while (m /= 10)cnt++; return cnt; } vector<int> radixSort(vector<int> vi, int n) { int d = max_cnt(vi, n); int multi = 1; for (int i = 1; i <= d; i++) { vector<vector<int> > temp(10, { 0 });//要调用push_back()所以每个桶放了个0，因此从 j=1 开始 for (int j = 0; j < n; j++) { int mask = (vi[j]/multi) % 10; temp[mask].push_back(vi[j]); } int k = 0; for (int i = 0; i < (int)temp.size(); i++) { for (int j = 1; j < (int)temp[i].size(); j++) { vi[k++] = temp[i][j]; } } multi *= 10; } return vi; } int main() { vector<int > s = { 1,2,3,5,6,8,4,4,-1 }; vector<int > s1 = { 1,2,3,5,6,8,4,4,-1 }; vector<int > s2 = { 1,2,3,5,6,8,4,4,-1 }; vector<int > s3 = { 1,2,3,5,6,8,4,4,-1,1,5,6,4,8,66,9 }; vector<int > s4 = { 12, 14, 54, 5, 6, 3, 9, 8, 47, 89 }; cout << s.size() << endl; vector<int > res1_1 = m_Insert1(s, 9);//插入排序1 vector<int > res1_2 = m_Insert2(s, 9);//插入排序2 vector<int > res2 = m_shellSort(s, 9);//希尔排序 vector<int > res3_1 = m_bobbleSort1(s, 9);//冒泡排序 vector<int > res3_2 = m_bobbleSort2(s, 9);//冒泡排序---改进1（记交换次数） vector<int > res3_3 = m_bobbleSort3(s, 9);//冒泡排序---改进2（记最后一次交换位置） m_quickSort(s1, 0, 8);//快速排序---右左右左.... vector<int > res4 = m_selectSort(s, 9);//选择排序----选出无序数列中最小值 m_heapSort(s2, 9);//堆排序，通过堆的思想找出最值（大堆，小堆） memetySort(s3, 0, 15);//归并排序，先递归，在合并。----每次分成两个子序列，对两个有序序列合并 //基数排序----个位、十位.....每次讲序列中符合的数放入相应的桶内，再依次取出 //如S4中（最大数为2位数，即循环 2 次：个位，十位）：个位时----0、1号桶为空，2号桶：12。3号桶：3。4号桶：14，54。5号桶：5。6号桶：6。7号桶：47。8号桶：8。9号桶：9，89 //依次取出：S4=12 3 14 54 5 6 47 8 9 89 //十位时----0号桶：3,5,6,8,9，1号桶：12，14。3号桶：空。4号桶：47。5号桶：54。6号桶：空。7号桶：空。8号桶：89。9号桶：空 //依次取出：S4=3 5 6 8 9 12 14 47 54 89 //很棒的想法 vector<int > res5 = radixSort(s4, 10); return 0; }