####排序算法
一、插入排序
（1）算法思维（以升序举例）：
对于一个曾经有序的序列，又来一个数x，从倒数第一个数进行比拟，如果x比这个数小，这个数就往后挪。
（2）代码实现
//O(N)最好程序-O(N*N)最坏逆序void insert_sort(int*a, int n){ for (int i = 0; i < n-1; ++i) { int end = i; int x = a[i+1]; while (end >= 0) { if (a[end] > x) { a[end+1] = a[end]; --end; } else { break; } } a[end + 1] = x; }}（3）改良：希尔排序
思维：插入排序在整体有序的状况下成果最好，于是希尔排序先预排序让序列先大体有序，最初进行插入排序来获得最好的成果。它的工夫复杂度大略为O(N^1.3)。
步骤：把数字分成gap个一组->对每组数据进行插入排序来达到大体有序的目标->对整体插入排序
//gap越小，越靠近有序。pow(n,1.3)void shell_sort(int* a, int n){ int gap = n; while (gap > 1) { gap = gap/3 + 1;//gap>1都是预排序，gap==1为间接插入排序 for (int i = 0; i < gap; ++i) { for (int j = i; j < n - gap; j += gap) { int end = j; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } } } }二、抉择排序
思维：在序列中每次都找到最小值和最大值，把它们放在应该的地位。
//O(N*N)void select_sort(int* a, int n){ //assert(a); int begin = 0, end = n - 1; while (begin < end) { int min_ = begin, max_ = end; for (int i = begin; i <= end; ++i) { if (a[i] < a[min_])min_ = i; if (a[i] > a[max_])max_ = i; } swap(&a[begin], &a[min_]); if (max_ == begin) { max_ = min_; } swap(&a[end], &a[max_]); ++begin; --end; }}三、堆排序
思维：应用堆的down操作来找到大堆中的最大值，把它替换到尾部，再对a[0]进行一个down。
//nlognvoid heap_sort(int* a, int n){ for (int i = (n - 2) / 2; i >= 0; --i) { heap_down(a, n, i); } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); heap_down(a, end, 0); --end; }}四、冒泡排序
思维：每次循环都确定一个最大值，先是最大的，放到尾部，其次是第二大的，直到没有产生替换，阐明排序曾经实现。
//O(n*n) 最好:n,遍历一次就晓得后果void bubble_sort(int* a, int n){ for (int i = 0; i < n; ++i) { int f = 0; for (int j = 0; j < n-i-1; ++j) { if (a[j] > a[j+1]) { f = 1; swap(&a[j], &a[j+1]); } } if (f == 0) { break; } }}五、疾速排序
(1)思维：每次排序找一个key，通过排序使得序列的右边数据都<=key，左边数据都>=key，递归解决。
void quick_sort(int* a, int begin, int end){ if (begin >= end) return; int keyi = quick1_sort(a, begin, end); quick1_sort(a + begin, begin, keyi - 1); quick1_sort(a + begin, keyi + 1, end); }//传统写法：抉择一个key，左边先走，右边再走，替换，直到l==rint quick1_sort(int* a, int begin, int end){ int l = begin; int r = end; int keyi = a[l]; while (l < r) { //左边先走 while (l < r && a[r] >= a[keyi]) { r--; } //当初的a[r]<key while (l < r && a[l] <= a[keyi]) { l++; } swap(&a[l], &a[r]); } swap(&a[keyi], &a[l]); keyi = l; return keyi;}//挖坑法int quick2_sort(int* a, int begin, int end){ int l = begin; int r = end; int key = a[begin]; int pit = begin; while (l < r) { //左边先走 while (l < r && a[r] >= key) { r--; } a[pit] = a[r]; pit = r;//这是新的坑 while (l < r && a[l] <= key) { l++; } a[pit] = a[l]; pit = l;//这是新的坑 } a[pit] = key; return pit;}//前后指针法int quick3_sort(int*a, int begin, int end){ int keyi = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { if (a[cur] < a[keyi]) { ++prev; if(prev != cur) swap(&a[prev], &a[cur]); } cur++; } swap(&a[prev], &a[keyi]); return prev;}在传统写法中，右边作key，为什么让左边先走？
为了保障找到的相遇的地位肯定是<=key，r停的地位肯定<= key;
r始终往左边走，直到遇到l，阐明这个地位左边的值都比Key大，相遇的地位是l上一轮停下来的，这里要么是key（第一轮），要么比key小（不是第一轮了，上一轮r换过去的），工夫复杂度为nlogn。
(2)优化
思维1：当key每次都是最大或者最小时复杂度最高，抉择一个值在两头的数能力有好的后果。
//优化1=key每次都是最小或者最大成果最差：有序或者靠近有序->1.随机选Key 2.三数选中int get_key(int* a, int begin, int end)//失去下标{ int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end])return mid; else if (a[begin] < a[end])return end; else return begin; } else { if (a[end] > a[begin])return begin; else if (a[mid] < a[end])return end; else return mid; }}思维2：当递归区间比拟小的时候，不再递归解决，而是用其余算法对小区间排序，这样能够大大减少递归的次数（80%）
void quick_sort(int* a, int begin, int end){ if (begin >= end)return; if (end - begin > 10)//80% { int keyi = quick1_sort(a, begin, end); quick1_sort(a + begin, begin, keyi - 1); quick1_sort(a + begin, keyi + 1, end); } else { insert_sort(a,end -begin+1 ); }}(3)快拍的非递归写法
递归转非递归的办法：1.间接改循环。2.应用栈来模仿（这样不必放心栈溢出，因为堆的空间比拟大）
void quick_sort_nor(int* a, int begin, int end){ stack<int>st; st.push(end); st.push(begin); while () { int l = st.top(); st.pop(); int r = st.top(); st.pop();//(l,key-i-1)(keyi+1,r) int keyi = quick1_sort(a, l, r); if (r > keyi + 1) { st.push(r); st.push(keyi + 1); } if (l < keyi - 1) { st.push(keyi - 1); st.push(l); } }}六、归并排序
（1）思维：先把序列递归分成小区间，再把小区间排成有序，接着把曾经有序的小区间进一步变成有序的区间。
void merge_sort(int* a, int n){ int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { exit(-1); } _merge_sort(a, 0, n - 1, temp); free(temp);}void _merge_sort(int* a, int begin, int end, int* temp){ if (begin >= end)return; int mid = (begin + end) / 2; _merge_sort(a, begin, mid, temp); _merge_sort(a, mid+1, end, temp); //归并，使小区间有序 int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { temp[i++] = a[begin1++]; } else { temp[i++] = a[begin2++]; } } while (begin1 <= end1) { temp[i++] = a[begin1++]; } while (begin2 <= end2) { temp[i++] = a[begin2++]; } memcpy(a + begin, temp + begin,(end - begin + 1)*sizeof(int));}(2)非递归写法
思维：把数组分成1个一组，2个一组......对每两个小组进行归并合成一个大的组。要留神边界问题。
对[i, i+gap-1]和[i+gap, i+2gap-1]归并；[i+2gap, i+3gap-1]和[i+3gap, i+4gap-1]归并......
void merge_sort_nor(int* a, int n){ int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { exit(-1); } int gap = 1; while (gap<n) { //i i+gap-1;i+gap i+2*gap-1; int j = 0; for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1, begin2 = i + gap, end2 = i + 2 * gap - 1; //修改边界 if (end1 >= n) { end1 = n - 1; //修改成不存在的区间 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else if (end2 >= n) { end2 = n - 1; } j = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2])//加个=，使他能够稳固 { temp[j++] = a[begin1++]; } else { temp[j++] = a[begin2++]; } } while (begin1 <= end1) { temp[j++] = a[begin1++]; } while (begin2 <= end2) { temp[j++] = a[begin2++]; } } memcpy(a, temp, 2*gap* sizeof(int)); gap *= 2; } free(temp); }七、相干概念
1.稳定性：绝对程序不变。eg: 1 2 3 3 4 2，在排序之后，2的绝对程序不变，5的绝对程序不变。
2.内排序：在内存上进行的排序
外排序：在磁盘上进行的排序
eg.有10亿个int整数，须要4G的空间，对这些数字排序。思维：为了进步速度，先把这些数字分成四份，把每一份放在内存外面归并排序再写入文件，之后对这些文件进行归并排序。（fprintf/fscanf)。
八、各个内排序算法比拟