直接排序与希尔排序
直接插入排序
我们在玩扑克牌的时候，每次抓一张牌都要放在适合的位置，比如我就喜欢左边大右边小，这就算是插入排序。
例：
加入给这个数组排序，我们先将2和3比较，然后排序成有序，再让7和有序的2和3比较，以此循环。
最后5和有序的2，3，7，9比较，先和9比较大小，比9小就与9交换位置，然后5在和7比较，比7小再与7交换位置，最后和3比较位置，比3大，那么就排序好了，不需要和2比较。
代码的实现思路也很简单：
这里交换数太麻烦了，可以用一个变量储存数据5，把9和7往后移，原本的数就会被覆盖掉，然后将储存的数放在指定的位置。
void sort() { int arr[] = { 2,3,7,9,5 }; int i = 0;//控制end int n = sizeof(arr)/sizeof(arr[0]); 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 } }
s>arr[end]的时候，不用让3覆盖end+1这个位置了，这里将5覆盖在了这个位置。
这个排序的效率是非常慢的。
时间复杂度：O（N2）
希尔排序
希尔排序是直接插入排序的优化：
希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
例如我们要将这组数从小到大排序：
9 8 7 6 5 4 3 2 1 0
gap = 3
黑色，红色，紫色分别是三组：
黑色组：9先和6比较，9比6大，交换他们，然后是9和3比较，交换，9和0比较，交换。
然后再进行红色和紫色的比较与交换：
我们发现这个顺序已经接近从大到小了，最后用直接插入排序让他变成正序就可以了。
先来一组数预处理的代码实现：
void Shellsort() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); int gap = 3; for (int i = 0; i < n - gap; i+=gap)//一组的排序 { int end = i; int sum = arr[end + gap]; while (end >= 0) { if (arr[end] > sum) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = sum; } }
如果所有组都算就需要在加一层循环：
void Shellsort() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); int gap = 3; for (int j = 0;j < gap;j++) { for (int i = j; i < n - gap; i += gap)//一组的排序 { int end = i; int sum = arr[end + gap]; while (end >= 0) { if (arr[end] > sum) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = sum; } } }
但是这样不好，三层循环很麻烦，那么我们再进行优化一下：
void Shellsort() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); int gap = 3; for (int i = 0; i < n - gap; i++) { int end = i; int sum = arr[end + gap]; while (end >= 0) { if (arr[end] > sum) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = sum; } }
改成这个样子就省了一层的循环，先交换第一组的9和6.然后end+1，就到了第二组交换第二组的8和5，以此类推，最后交换的是，3和0。
这是多组并排的方式，并且gap不知道应该定义多大，gap多大也间接影响到最后一次直接插入排序的效率，所以需要再次改进：
那么gap等于多少是最好的呢？
gap越大，虽然大的数据和小的数据排序越快，但是顺序越乱，gap越小则相反。
那么让最初的gap等于数组长度，每次除以3，进行越来越细致的预处理。
void Shellsort() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int n = sizeof(arr) / sizeof(arr[0]); int gap = n; while (gap > 1) { gap = gap / 3 + 1;//+1是为了最后能等于1，也可以是gap=gap/2，这两种写法效率最高 for (int i = 0; i < n - gap; i++)//这里就是以gap为一组的进行预处理排序 { int end = i; int sum = arr[end + gap]; while (end >= 0) { if (arr[end] > sum) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = sum; } } }
当gap等于1的时候就等于插入排序了。
希尔排序的时间复杂度目前算的大约是O(N1.3)。
具体的时间复杂度是多少并没有推理过程。
选择排序
选择排序
选择排序是从左向右或者是从右向左开始选择一个最小的数然放在左边或者是右边，然后再选剩下的数中最小的数放在左边或者是右边：
这里我们选择对这个数组进行升序，第一次在整个数组里面找最小的，选择的是1，放在最左边，然后第二次在5 6 8 4中找最小的，选择4，然后饭挂在5的前面，5 6 8往后移。
以此类推，直到走到尽头为止。
代码实现：
void Swap(int* a,int* b) { int c = *a; *a = *b; *b = c; } void selection_sort() { int arr[] = { 1,5,7,9,8,3,4,2,6,0 }; int n = sizeof(arr) / sizeof(arr[0]); int start = 0;//开头的下标 int end = n - 1;//结束的下标 while (start < end) { int min = start; int max = start; for (int i = start + 1; i <= end; ++i)//i=start + 1是因为第一个位置已经给min和max了 { if (arr[i] < arr[min]) { min = i;//找到最小的数下标就传给min } if (arr[i] > arr[max]) { max = i;//找到最大的数的下标 } } Swap(&arr[start], &arr[min]);//将最小的值放在前面 if (max == start)//对于max还是等于start的情况下进行修正，因为上面已经将min位置的和start位置的进行了交换 { max = min; } Swap(&arr[end], &arr[max]);//将最大的值放在后面 start++; end--; } }
这段代码是小的放前面，大的放后面，从两头开始找，直到找完整个数组为止。
时间复杂度为O(N2)
堆排序
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
