本篇博客实现了 1.冒泡排序 2.冒泡排序的一种优化(当某次冒泡没有进行交换时，退出循环) 3.选择排序 4.归并排序 5.快速排序。
主要是源码的实现，并将自己在敲的过程中所遇到的一些问题记录下来。
全局定义与相关声明：
#include#include #include using namespace std;int num[100005]; //存储数组void swap1(int i, int j) //交换函数swap{ int t = num[i]; num[i] = num[j]; num[j] = t;}/*Printnum 输出*/void Printnum(int n) //输出排序完成的数组{ for (int i = 1; i <= n; i++) { cout << num[i] << " "; } cout << endl;}
1.冒泡排序
/*Bubble_Sort 冒泡排序*/void Bubble_Sort(int n){ int i, j; for (i = 1; i <= n; i++) //遍历n次 { for (j = 1; j <= n-i; j++) //每次都把最大数往后排，缩小范围 { if (num[j] > num[j+1]) { swap1(j, j+1); } } }} 冒泡的思想：不断把范围中的最大数往后排，排完之后缩小范围；以上过程执行n次。
个人小结：思想很简单，但是太久不碰真的会忘记。
2.冒泡排序的优化
void Bubble_Sort_Better(int n){ int i, j; for (i = 1; i <= n; i++) { bool flag = true; for (j = 1; j <= n-i; j++) { if (num[j] > num[j+1]) { flag = false; swap1(j, j+1); } } if (flag) break; //某一次遍历没有发生交换时，结束 }} 优化的思想：当某一次冒泡没有交换任何数时，则说明当前范围内序列有序，结束循环。
3.选择排序
/*Selection_Sort 选择排序*/void Selection_Sort(int n){ int i, j; int rcd; for (i = 1; i <= n; i++) { rcd = i; for (j = i+1; j <= n; j++) { if (num[j] < num[rcd]) //找出i+1=>n范围内的最小元并前移 { rcd = j; } } swap1(i, rcd); }} 思想：找出范围i => n内最小的数，用rcd(初始化为i)记录其位置，之后与寻找范围内的第一个数num[i]进行交换，保证i+1 => n的所有数均大于num[i]。
4.归并排序：
/*Merge_Sort 归并排序*/int temp[100005];void Merge_Array(int l1, int r1, int l2, int r2){ int p1 = l1; int p2 = l2; int i = 1; memset(temp, 0, sizeof(temp)); for (i = l1; i <= r2; i++) { if (p1 > r1) { temp[i] = num[p2++]; continue; } if (p2 > r2) { temp[i] = num[p1++]; continue; } if (num[p1] < num[p2]) { temp[i] = num[p1++]; continue; } else { temp[i] = num[p2++]; continue; } } for (i = l1; i <= r2; i++) { num[i] = temp[i]; } }void Merge_Sort(int l, int r){ if (l < r) { int mid = (l+r)/2; Merge_Sort(l, mid); //l => mid Merge_Sort(mid+1, r); //mid+1 => r Merge_Array(l, mid, mid+1, r); //l => mid => mid+1 => r }} 思想可以参考：
大概的思路是，先并后归，将范围二分，分别递归排序之后再进行合并(利用一个额外的数组temp)。
个人小结：
1.看似简单，实现起来总是会出问题；动手吧。
2.一定要注意：递归选取的范围，取了mid = (l+r)/2之后，左边的一半范围为[l => mid]，右边的一半范围为[mid+1 => r]。原因可以考虑以下情况：两个数3 1进行排序，mid = 1，如果选取的范围为[l => mid-1]和，则会出现死循环。
5.QuickSort快速排序
int Quick_Sort_Adjust(int l, int r){ int key = l; //选取第一个元素为基准值 int a, b; a = l+1; b = r; while (a < b) { bool out_bound = false; while (1) { if (num[a] > num[key]) break; a++; if (a > r) { out_bound = true; break; } } while (1) { if (num[b] < num[key]) break; b--; if (b < l) { out_bound = true; break; } } if (out_bound || a >= b) break; //如果出现越界或a>=b直接结束 swap1(a, b); a++; b--; } swap1(key, a-1); return a-1;}void Quick_Sort(int l, int r){ if (l < r) { int mid = Quick_Sort_Adjust(l, r); Quick_Sort(l, mid-1); //l => mid-1 Quick_Sort(mid+1, r); //mid+1 => r }} 思想可以参考：
思路上文讲的很清楚了，建议在纸上模拟以下四种情况：
1.n = 71 3 1 2 -1 8 92.n = 71 1 1 1 1 1 13.n = 77 6 5 4 3 2 14.n = 77 1 1 1 1 1 1
个人小结：
1.同样的，自己敲一遍能够发现一堆问题。
2.一定要注意，当出现以下两种情况时：(1)i>j(这里的代码是a>b) (2)i、j越界 应该立即退出循环。
3.递归范围的选择，在基准值num[key]和num[mid]交换之后，接下来的递归范围应该为[l => mid-1]和[mid+1 => r]，因为[l => mid-1]范围内的所有值都小于num[mid]，[mid+1 => r]内的所有值都大于num[mid]；如果选取范围对mid取等，会出现上文中两个数(如 3 1)的死循环。
4.这里选择的基准是第一个数，快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用别的方法排序以减小递归深度。
完整代码如下：
//// main.cpp// Sort//// Created by wasdns on 16/12/25.// Copyright © 2016年 wasdns. All rights reserved.//#include#include #include using namespace std;/*存储数组定义*/int num[100005];void swap1(int i, int j){ int t = num[i]; num[i] = num[j]; num[j] = t;}/*Printnum 输出*/void Printnum(int n){ for (int i = 1; i <= n; i++) { cout << num[i] << " "; } cout << endl;}/*Bubble_Sort 冒泡排序*/void Bubble_Sort(int n){ int i, j; for (i = 1; i <= n; i++) //遍历n次 { for (j = 1; j <= n-i; j++) //每次都把最大数往后排，缩小范围 { if (num[j] > num[j+1]) { swap1(j, j+1); } } }}void Bubble_Sort_Better(int n){ int i, j; for (i = 1; i <= n; i++) { bool flag = true; for (j = 1; j <= n-i; j++) { if (num[j] > num[j+1]) { flag = false; swap1(j, j+1); } } if (flag) break; //某一次遍历没有发生交换时，结束 }}/*Selection_Sort 选择排序*/void Selection_Sort(int n){ int i, j; int rcd; for (i = 1; i <= n; i++) { rcd = i; for (j = i+1; j <= n; j++) { if (num[j] < num[rcd]) //找出i+1=>n范围内的最小元并前移 { rcd = j; } } swap1(i, rcd); }}/*Merge_Sort 归并排序*/int temp[100005];void Merge_Array(int l1, int r1, int l2, int r2){ int p1 = l1; int p2 = l2; int i = 1; memset(temp, 0, sizeof(temp)); for (i = l1; i <= r2; i++) { if (p1 > r1) { temp[i] = num[p2++]; continue; } if (p2 > r2) { temp[i] = num[p1++]; continue; } if (num[p1] < num[p2]) { temp[i] = num[p1++]; continue; } else { temp[i] = num[p2++]; continue; } } for (i = l1; i <= r2; i++) { num[i] = temp[i]; } }void Merge_Sort(int l, int r){ if (l < r) { int mid = (l+r)/2; Merge_Sort(l, mid); //l => mid Merge_Sort(mid+1, r); //mid+1 => r Merge_Array(l, mid, mid+1, r); //l => mid => mid+1 => r }}/*Quick_Sort 快速排序*/int Quick_Sort_Adjust(int l, int r){ int key = l; //选取第一个元素为基准值 int a, b; a = l+1; b = r; while (a < b) { bool out_bound = false; while (1) { if (num[a] > num[key]) break; a++; if (a > r) { out_bound = true; break; } } while (1) { if (num[b] < num[key]) break; b--; if (b < l) { out_bound = true; break; } } if (out_bound || a >= b) break; //如果出现越界或a>=b直接结束 swap1(a, b); a++; b--; } swap1(key, a-1); return a-1;}void Quick_Sort(int l, int r){ if (l < r) { int mid = Quick_Sort_Adjust(l, r); Quick_Sort(l, mid-1); //l => mid-1 Quick_Sort(mid+1, r); //mid+1 => r }}int main(){ int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> num[i]; } int option; cin >> option; if (option == 1) { cout << "Bubble_Sort" << endl; Bubble_Sort(n); } else if (option == 2) { cout << "Bubble_Sort_Better" << endl; Bubble_Sort_Better(n); } else if (option == 3) { cout << "Selection_Sort" << endl; Selection_Sort(n); } else if (option == 4) { cout << "Merge_Sort" << endl; Merge_Sort(1, n); } else if (option == 5) { cout << "Quick_Sort" << endl; Quick_Sort(1, n); } Printnum(n); return 0;}
2016/12/26