首页 > 代码库 > 排序 之 快排and归并<时间复杂度>----掌握思想和过程
排序 之 快排and归并<时间复杂度>----掌握思想和过程
俗话说：天下武功无坚不破，唯快不破。对于算法当然也是要使用时间最短、占用空间最小的算法来实现了。
注意：我代码里面打的备注仅供参考，建议不要背模板（因为没有固定的模板），可以写一个数列按着代码跑两圈或者把代码改一下输出每次排序后的结果。
总之，师傅领进门，修行在个人。奋斗把！骚年！
※冒泡排序、选择排序：（不稳定，时间复杂度 O(n^2)）
1 #include "cstdio" 2 #include "iostream" 3 using namespace std; 4 5 void bubble_sort (int *a, int n) { 6 int t; 7 for (int i = 0; i < n - 1; ++i) { 8 for (int j = 0; j < n - i - 1; ++j) { 9 if (a[j] > a[j + 1]) {10 t = a[j];11 a[j] = a[j + 1];12 a[j + 1] = t;13 }14 }15 }16 }17 18 int main () {19 int n, a[999];20 cin >> n;21 for (int i = 0; i < n; ++i)22 cin >> a[i];23 bubble_sort (a, n);24 for (int i = 0; i < n; ++i)25 cout << a[i] << " ";26 cout << endl;27 return 0;28 }
1 #include "cstdio" 2 #include "iostream" 3 using namespace std; 4 5 void selection_sort (int *a, int n) { 6 int t; 7 for (int i = 0; i < n; ++i) { 8 for (int j = i; j < n; ++j) { 9 if (a[i] > a[j]) {10 t = a[j];11 a[j] = a[i];12 a[i] = t;13 }14 }15 }16 }17 18 int main () {19 int n, a[999];20 cin >> n;21 for (int i = 0; i < n; ++i)22 cin >> a[i];23 selection_sort (a, n);24 for (int i = 0; i < n; ++i)25 cout << a[i] << " ";26 cout << endl;27 return 0;28 }
如果说冒泡和选择排序都没有弄明白的话，那你对于排序可以只记个sort函数和头文件就行了。
※这里是下面两个基础快排的合并版（没有注释）：（不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)）
1 #include <cstdio> 2 #include <iostream> 3 const int maxn = 1e6 + 10; 4 using namespace std; 5 int a[maxn]; 6 void quick_sort_left (int l, int r) { 7 if (l >= r) return ; 8 int i = l, j = r, key = a[l]; 9 while (i < j) {10 while (i < j && a[j] >= key) j--;11 a[i] = a[j];12 while (i < j && a[i] <= key) i++;13 a[j] = a[i];14 }15 a[i] = key;16 quick_sort_left (l, i - 1);17 quick_sort_left (i + 1, r);18 }19 void quick_sort_right (int l, int r) {20 if (l >= r) return ;21 int i = l, j = r, key = a[r];22 while (i < j) {23 while (i < j && a[i] <= key) i++;24 a[j] = a[i];25 while (i < j && a[j] >= key) j--;26 a[i] = a[j];27 }28 a[j] = key;29 quick_sort_right (l, i - 1);30 quick_sort_right (i + 1, r);31 32 }33 void quick_sort_anyone (int l, int r) {34 int i = l, j = r, key = a[l + (r - l) / 2];35 int t;36 while (i < j) {37 while (i < r && a[i] < key) i ++;38 while (j > l && a[j] > key) j --;39 if (i <= j) {40 t = a[i];41 a[i] = a[j];42 a[j] = t;43 44 i ++;45 j --;46 }47 }48 if (i < r) quick_sort_anyone (i, r);49 if (j > l) quick_sort_anyone (l, j);50 }51 int main () {52 int n;53 cin >> n;54 for (int i = 0; i< n; ++i)55 cin >> a[i];56 // quick_sort_left (0, n - 1);57 // quick_sort_right (0, n - 1);58 // quick_sort_anynoe (0, n - 1);59 for (int i = 0; i < n; ++i)60 cout << a[i] << " ";61 cout<< endl;62 return 0;63 }
※基础快排1----选择左右两边为基准排序：（不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)）
1 #include <bits/stdc++.h>//万能头文件 2 using namespace std; 3 4 void quick_sort (int a[], int l, int r) { 5 if (l >= r) return ; 6 int i = l, j = r; 7 int key = a[l]; 8 while (i < j) { ///这里不能带等号，，死循环 9 while (i < j && a[j] >= key) {//<=是找有相同数字的时候10 j --; //选的左边作为key，所以就从右边开始.11 }12 a[i] = a[j]; //找到一个该交换的时候退出交换。13 while (i < j && a[i] <= key) { //<=是找有相同数字的时候14 i ++;15 }16 a[j] = a[i]; //同上17 }18 a[i] = key;19 quick_sort (a, l, i - 1);////应该可以交换位置，因为这两个是等效的，20 quick_sort (a, i + 1, r);////就是排序上次key两的的值21 }22 23 int main () {24 int n;25 int a[999];26 scanf ("%d", &n);27 for (int i = 0; i < n; ++i)28 {29 scanf ("%d", &a[i]);30 }31 quick_sort (a, 0, n - 1);32 for (int i = 0; i < n; ++i)33 {34 printf("%d ", a[i]);35 }36 printf("\n");37 return 0;38 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 void quick_sort (int a[], int l, int r) { 5 if (l >= r) return ; 6 int i = l, j = r; 7 int key = a[r]; 8 while (i < j) { ///这里不能带等号，，死循环 9 while (i < j && a[i] <= key) {//<=是找有相同数字的时候10 i ++; //选的右边作为key，所以就从左边开始.11 }12 a[j] = a[i]; //找到一个该交换的时候退出交换。13 while (i < j && a[j] >= key) { //<=是找有相同数字的时候14 j --;15 }16 a[i] = a[j]; //同上17 }18 a[j] = key;//-----先替换的a[j]，所以在这里补上.19 quick_sort (a, l, i - 1);////可以交换位置，是等效的20 quick_sort (a, i + 1, r);////就是排序上次key两的的值21 }22 23 int main () {24 int n;25 int a[999];26 scanf ("%d", &n);27 for (int i = 0; i < n; ++i)28 {29 scanf ("%d", &a[i]);30 }31 quick_sort (a, 0, n - 1);32 for (int i = 0; i < n; ++i)33 {34 printf("%d ", a[i]);35 }36 printf("\n");37 return 0;38 }
注意：快排函数最后递归的时候可以按j也可以按i，因为最后满足 i == j; 理解代码里面等号的取舍！
※基础快排2----选择任意数字为基准排序：（不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)）
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 5 void quick_sort (int *a, int l, int r) { 6 int i = l, j = r, key = a[l + (r - l) / 2]; 7 //int key = a[r]; 8 //从数列里面任意找一个key就行 9 int t;10 while (i < j) {11 while (i < r && a[i] < key) i ++;12 //不能写成a[i] <= key，会跳过一些数字,导致不能排序13 while (j > l && a[j] > key) j --;14 //这两个while可以交换位置，以左右为基准的快排不能交换15 if (i <= j) {16 t = a[i];17 a[i] = a[j];18 a[j] = t;19 20 i ++;21 j --;22 }23 }24 if (i < r) quick_sort (a, i, r);25 if (j > l) quick_sort (a, l, j);26 }27 28 int main () {29 int n;30 int a[999];31 cin >> n;32 for (int i = 0; i < n; ++i)33 cin >> a[i];34 quick_sort (a, 0, n - 1);35 for (int i = 0; i < n; ++i)36 cout << a[i] << " ";37 cout << endl;38 return 0;39 }40 41 Quick_sort_anyone
简述：快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
※归并排序：（稳定，时间复杂度 O(nlog n)）
1 #include <stdio.h>//归并排序 2 #include <stdlib.h> 3 void merge(int a[],int b[], int f, int mid, int e) 4 {//合并两个数组 5 int i = f, j = mid + 1, k = f; 6 while(i <= mid && j <= e)//注意衔接 7 { 8 if(a[i] >= a[j]) //谁大就不把谁装到前面 9 b[k++] = a[j++];10 else11 b[k++] = a[i++];12 }13 while(i <= mid)//前半个有剩余14 b[k++] = a[i++];15 while(j <= e)//后半个有剩余16 b[k++] = a[j++];17 for(i = f; i <= e; i++) //最后再还给a18 a[i] = b[i];19 }20 void mergesort(int a[], int b[], int f, int e)//内部使用递归21 {22 if(f < e)23 {24 int mid = (e + f) / 2;25 mergesort(a, b, f, mid); //拆分到很小很小26 mergesort(a, b, mid + 1, e);27 merge(a, b, f, mid, e);28 }29 }30 int main(){31 int n;32 int a[999];33 int i, b[999];34 scanf ("%d", &n);35 for (int i = 0; i < n; ++i)36 scanf ("%d", &a[i]);37 mergesort(a, b, 0, n - 1);38 for(i = 0; i < n; i++)39 printf("%d ", a[i]);40 printf("\n");41 return 0;42 }
简述：将数组拆分为两组，对于一个数组来说，两个数组要好排的多...依次类推，当分到只要一个元素的时候，我们就认为是有序的，然后再挨个合并相邻的数组。我们可以先递归分解，然后再归并排序。
欢迎码友评论，一起成长。
排序 之 快排and归并<时间复杂度>----掌握思想和过程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。