冒泡排序
void Swap(int* a, int* b) { int c = *a; *a = *b; *b = c; } void bubbling() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); int x = 1; for (int j = 0; j < n; j++) { for (int i = 0; i < n - 1 - j; i++) { if (arr[i] > arr[i + 1]) { Swap(&arr[i], &arr[i + 1]); x = 0; } } if (x == 1)//如果x没有被置为0就说明没有可以交换的数据了 { break; } } }
这个排序是我最早接触的排序。
时间复杂度为：O(N2)
虽然很慢，但是很容易理解。
快速排序
基本思想：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快排有三种方法。（原理都是类似的）
hoare法
这个版本的方法是先选择一个key值，一般是在第一个或者是最后一个位置，然后两个变量从头和尾向中间走，相遇就会停下。
例：
这里key我选的是数组中第一个值，R找比key小的，L找比key大的，如果R找到的值比key找到的小就与L位置进行交换（但是key值只在R与L相遇才会换位置），就像这样，假如R先走，就先和key比较：
这里R走了两步，因为8比6大，10比6大，现在R的位置是4，比6小，停下，这里不进行交换，然后L走，L到7的位置停下，因为7比6大，然后R和L的位置进行交换。
然后R走一步到3的位置停下，L走一步，发现没有比key大，再走一步与R相遇，这时将R与L相遇的位置与key值的位置进行交换。
那么怎么保证L与R相遇的位置的值一定小于key呢？答案是R先走。
R停下，说明撞到了L，L虽然是找比key大的，但是在R走之前L与R位置的值一定互换了，就算L一直没动，就说明所有的值都比key大。
L停下，撞到了R，R是找小，撞到R，R的位置一定是小于key的数，如果R没动，说明所有数都比key小。
同理，如果key在右边第一个值，L先走。
排序完成之后我们发现6的前面和后面正好分成了两个区间，6的位置也是不用在进行移动的，这就是但趟排序，然后再用将这组数的前后区间进行相同方法的排序就可以了，直到剩下最后一个数为止。
以此类推，其实就是一个递归二叉树的原理。
代码实现：
#include <stdio.h> void Swap(int* a,int* b) { int c = *a; *a = *b; *b = c; } int single_row(int* a, int start, int end)//单趟排序 { int key = start;//让key变成头部位置 while (start < end) { while (a[end] >= a[key] && end > start)//如果这里不是>=key可能会会产生死循环 { end--; } while (a[start] <= a[key] && end > start) { start++; } if (start < end)//没有相遇就交换 { Swap(&a[start], &a[end]); } } Swap(&a[key], &a[end]);//当R与L相遇交换key和相遇位置的数据 return end;//返回相遇的位置 } void Quicksort(int* a, int start, int end)//调用一次这个函数就等于使用一次单排的逻辑 { if (start >= end)//如果剩余一个数或者是没有数据就不用排序了 { return; } int key = single_row(a, start, end);//单排，返回值是已经排序好的数值的位置 Quicksort(a, start, key - 1);//左区间 Quicksort(a, key + 1, end);//右区间 } int main() { int arr[] = { 6,2,7,1,3,4,10,8 }; int n = sizeof(arr) / sizeof(arr[0]); Quicksort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
这棵二叉树的深度是logN，每层单排的时间复杂度是O(N).
总体时间复杂度是O(N*logN), 但是这种情况只发生在相遇的地方是在数组中间左右位置的地方。
那么如果每次相遇的地方总是在头或者是尾会怎么样呢？
红色是key的位置，左边树一直都是空的，也就是说这棵树的深度是N,时间复杂度就是O(N2),这样还能能被称为快排吗？不仅仅如此，还会造成栈溢出的情况。
所以我们要优化一下。
快排的优化
有两个优化的地方：
1.key值的调整
2.避免给二叉树的后三层排序
key值的调整取中间数明显是最好的，不过数组中想取中间数很困难，不能让key每次都取数组中间的数，因为key随意位移单排的整体代码都会被更改，如果想让key的数更换直接让中间的数与开头的数交换就可以了，但是如果换过来的数正好是最小或者是最大的数呢？那么就又会发生上面的事情，所以要三数取中法，选择开头的数和中间的数，末尾的数，然后比大小，选择中间大的数。
避免二叉树的后三层是因为最后一层的结点占了整个二叉树的50%，倒数第二层占了25%，倒数第三层占了12.5%，如果在倒数第四层的地方用直接插入排序会更好，因为每次排序都会接近更有序，所以用直接插入排序更划算。
因为单排要等最后一个数才会停止，所以可以推理出倒数第四层为8个数。
代码实现
#include <stdio.h> void sort(int* arr, int n) { int i = 0;//控制end for (i = 0; i < n - 1; i++) { int end = i;//这个是两个数比较中的第一个数 int s = arr[end + 1];//保留的是两个数的后面一个数 while (end >= 0) { if (arr[end] > s)//比较两个数的大小 { arr[end + 1] = arr[end];//如果不是从大到小就重新排序 end--; } else { break; } } arr[end + 1] = s;//如果顺序没错就将储存起来的数据放到指定位置，这么写的好处还有一个是end最坏的情况会到-1 } } void Swap(int* a, int* b) { int c = *a; *a = *b; *b = c; } int middle(int* a, int start, int end)//取中间数 { int mid = (start + end) / 2; if (a[start] < a[mid]) { if (a[start] > a[end])//mid最大，end最小 { return start; } else if (a[end] > a[mid])//end最大，start最小 { return mid; } else//mid最大，start最小 { return end; } } else//a[start] >= a[mid] { if (a[end] > a[start])//end最大，mid最小 { return start; } else if(a[mid] > a[end])//start最大，end最小 { return mid; } else//start最大，mid最小 { return end; } } } int PartSort(int* a, int start, int end)//单趟排序 { int key = middle(a, start, end); Swap(&a[key], &a[start]);//交换中间数和第一个数的位置 while (start < end) { while (a[end] >= a[key] && end > start)//如果这里不是>=key可能会会产生死循环 { end--; } while (a[start] <= a[key] && end > start) { start++; } if (start < end)//没有相遇就交换 { Swap(&a[start], &a[end]); } } Swap(&a[key], &a[end]);//当R与L相遇交换key和相遇位置的数据 return end;//返回相遇的位置 } void Quicksort(int* a, int start, int end)//调用一次这个函数就等于使用一次单排的逻辑 { if (start >= end)//如果剩余一个数或者是没有数据就不用排序了 { return; } if (end - start <= 8) { sort(a + start, end - start + 1);//第一个参数因为左右区间的问题，第二个参数要加一的原因是要跳过已经排序号位置的数 } else { int key = PartSort(a, start, end);//单排，返回值是已经排序好的数值的位置 Quicksort(a, start, key - 1);//左区间 Quicksort(a, key + 1, end);//右区间 } } int main() { int arr[] = { 6,2,7,1,3,4,10,8 }; int n = sizeof(arr) / sizeof(arr[0]); Quicksort(arr, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
