堆排序
堆排序是利用树的结构进行的，常常用于选出最大/最小的N个数，效率很高
树可以用链表表示，也可以用数组表示，这里我们先用数组来实现堆排序
首先我们要先把一个数组构造成一个堆，只有成为了一个堆之后才能进行向上/向下调整
将问题一个一个细分，因为一个乱的数如果直接从根开始进行向上/向下进行排序的话肯定是不行的，所以我们可以从最后一个非叶子节点开始往前进行向上调整，而这里为什么要从最后一个非叶子节点开始呢？因为单个叶子节点不需要调整，也无法进行调整，如图，第一个非叶子节点就是3，从而对3和6进行调整，一直到1位置为止，这时候就已经把数组排成了一个堆了。
而如何进行向上/向下调整呢？
对于向下调整而言，调成一个小堆我，就是父亲节点一定小于孩子节点。
而第一个问题就是如何找到左右孩子中较小的那一个呢？为了代码的简洁，可以直接找到左孩子，而右孩子就是左孩子+1，child=parent*2+1，以下为代码实现:
1. //向下调整(小堆) 2. void AdjustDown(int *a, int n, int parent) { 3. int child = parent * 2 + 1;//左孩子，右孩子为左孩子+1 4. while (child < n) { 5. //child+1不能大于n，然后再选出左右孩子中小的那一个 6. if (child + 1 < n && a[child + 1] < a[child]) { 7. child++;//拿到右孩子 8. } 9. if (a[child] < a[parent]) { 10. //如果孩子节点小于父亲节点，则进行交换 11. Swap(&a[child], &a[parent]); 12. //父亲和孩子继续交换，继续向下调整 13. parent = child; 14. child = parent * 2 + 1; 15. } else { 16. break; 17. } 18. } 19. }
交换函数Swap:
1. void Swap(int *child, int *parent) { 2. int tmp = *child; 3. *child = *parent; 4. *parent = tmp; 5. }
现在就可以将数组构造成堆了，代码实现:
1. void CreateHeap(int *a, int n) { 2. //找到最后一个非叶子节点的节点 3. for (int i = (n - 1 - 1) / 2; i >= 0; i--) { 4. AdjustDown(a, n, i); 5. } 6. }
总代码:
1. #include <stdio.h> 2. 3. void Swap(int *child, int *parent) { 4. int tmp = *child; 5. *child = *parent; 6. *parent = tmp; 7. } 8. 9. //堆排序 10. 11. //向下调整(小堆) 12. void AdjustDown(int *a, int n, int parent) { 13. int child = parent * 2 + 1;//左孩子，右孩子为左孩子+1 14. while (child < n) { 15. //child+1不能大于n，然后再选出左右孩子中小的那一个 16. if (child + 1 < n && a[child + 1] < a[child]) { 17. child++;//拿到右孩子 18. } 19. if (a[child] < a[parent]) { 20. //如果孩子节点小于父亲节点，则进行交换 21. Swap(&a[child], &a[parent]); 22. //父亲和孩子继续交换，继续向下调整 23. parent = child; 24. child = parent * 2 + 1; 25. } else { 26. break; 27. } 28. } 29. } 30. 31. //建堆 32. void CreateHeap(int *a, int n) { 33. //找到最后一个非叶子节点的节点 34. for (int i = (n - 1 - 1) / 2; i >= 0; i--) { 35. AdjustDown(a, n, i); 36. } 37. } 38. 39. int main(void) { 40. int arr[] = { 3, 8, 9, 18, 7, 5, 10, 87, 21, 99, 76, 100 }; 41. CreateHeap(arr, 12); 42. for (int i = 0; i < 12; i++) { 43. printf("%d ", arr[i]); 44. } 45. return 0; 46. }
运行结果
画出树的结构为:
可以看出，这个数组已经变成一个小堆了。
接下来就可以进行堆排序了，那么如何进行堆排序呢？
如果要排升序，就建立一个大堆，选出来最大的数，然后最后一个数和第一个数交换，再把最后一个数不看作堆里的数1，进行向下调整即可
代码实现:
1. void HeapSort(int *a, int n) { 2. for (int i = (n - 1 - 1) / 2; i >= 0; i--) { 3. AdjustDown(a, n, i); 4. } 5. int end = n - 1; 6. while (end >= 0) { 7. Swap(&a[0], &a[end]); 8. AdjustDown(a, end, 0); 9. end--; 10. } 11. }
运行结果:
这样就排序成功了。
总代码:
1. #include <stdio.h> 2. 3. void Swap(int *child, int *parent) { 4. int tmp = *child; 5. *child = *parent; 6. *parent = tmp; 7. } 8. 9. //堆排序 10. 11. //向下调整(小堆) 12. void AdjustDown(int *a, int n, int parent) { 13. int child = parent * 2 + 1;//左孩子，右孩子为左孩子+1 14. while (child < n) { 15. //child+1不能大于n，然后再选出左右孩子中小的那一个 16. if (child + 1 < n && a[child + 1] > a[child]) { 17. child++;//拿到右孩子 18. } 19. if (a[child] > a[parent]) { 20. //如果孩子节点小于父亲节点，则进行交换 21. Swap(&a[child], &a[parent]); 22. //父亲和孩子继续交换，继续向下调整 23. parent = child; 24. child = parent * 2 + 1; 25. } else { 26. break; 27. } 28. } 29. } 30. 31. //建堆 32. void CreateHeap(int *a, int n) { 33. //找到最后一个非叶子节点的节点 34. for (int i = (n - 1 - 1) / 2; i >= 0; i--) { 35. AdjustDown(a, n, i); 36. } 37. } 38. 39. //堆排序(大堆的条件下),进行升序 40. void HeapSort(int *a, int n) { 41. for (int i = (n - 1 - 1) / 2; i >= 0; i--) { 42. AdjustDown(a, n, i); 43. } 44. int end = n - 1; 45. while (end >= 0) { 46. Swap(&a[0], &a[end]); 47. AdjustDown(a, end, 0); 48. end--; 49. } 50. } 51. 52. int main(void) { 53. int arr[] = { 3, 8, 9, 18, 7, 5, 10, 87, 21, 99, 76, 100 }; 54. HeapSort(arr, 12); 55. for (int i = 0; i < 12; i++) { 56. printf("%d ", arr[i]); 57. } 58. return 0; 59. }
选择排序
选择排序，顾名思义就是选择某个数进行排序，这里我们可以遍历一次数据，找到最小值和最大值，将最小值放在第一个位置，最大值放在最后一个位置，然后再将区间缩小，一次类推，但这里会有一个bug，那就是当第一个数就是最大值的时候是无法正确进行排序的。
这时候就需要进行修正
解决方法就是加一个判断，如果begin==maxi，那么maxi=mini
代码实现
1. #include <stdio.h> 2. 3. void Swap(int* child, int* parent) { 4. int tmp = *child; 5. *child = *parent; 6. *parent = tmp; 7. } 8. 9. void SelectSort(int* a, int n) { 10. int begin = 0, end = n - 1; 11. while (end > begin) { 12. int mini = begin, maxi = begin; 13. for (int i = begin; i <= end; i++) { 14. if (a[i] < a[mini]) { 15. mini = i; 16. } 17. if (a[i] > a[maxi]) { 18. maxi = i; 19. } 20. } 21. Swap(&a[begin], &a[mini]); 22. if (begin == maxi) { 23. maxi = mini; 24. } 25. Swap(&a[end], &a[maxi]); 26. end--; 27. begin++; 28. } 29. } 30. 31. int main(void) { 32. int arr[] = { 100, 8, 6, 89, 26, 83, 52, 12, 90, 0 }; 33. SelectSort(&arr, 10); 34. for (int i = 0; i < 10; i++) { 35. printf("%d ", arr[i]); 36. } 37. return 0; 38. }
直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一
个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
实际中我们玩扑克牌时，就用了插入排序的思想
从要插入的位置开始，设这个位置为end,用该位置的数值从后往前比较，如果能找到比它小的数，则a[end+1]=x;
代码实现:
1. #include <stdio.h> 2. 3. void InsertSort(int *a, int n) { 4. for (int i = 0; i < n - 1; i++) { 5. int end = i; 6. int x = a[end + 1]; 7. while (end >= 0) { 8. if (a[end] > x) { 9. a[end + 1] = a[end]; 10. end--; 11. } else { 12. break; 13. } 14. } 15. a[end + 1] = x; 16. } 17. } 18. 19. int main(void) { 20. int arr[] = {100, 520, 123, 98, 56, 23, 87, 12, 66, 99}; 21. InsertSort(arr, 10); 22. for (int i = 0; i < 10; i++) { 23. printf("%d ", arr[i]); 24. } 25. return 0; 26. }
运行结果:
希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个
组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工
作。当到达=1时，所有记录在统一组内排好序。
希尔排序其实就是在直接插入排序的基础上进行了改良，直接插入排序的快慢取决于数组是否接近有序，是的话则很快，反之较慢，而希尔排序就是先将数组接近有序，再进行直接插入排序
如图所示，当gap等于2的时候，4 2 5 8 5为一组，1 3 9 6 7为一组，对这两组数据进行排序，可以使得数组的数据接近有序，当gap越大，越接近无序，反之则接近有序，当gap=1的时候，就是直接插入排序了，又因为gap也是数据的组数，所以可以操作gap来进行排序
代码实现：
1. #include <stdio.h> 2. 3. void ShellSort(int *a, int n) { 4. int gap = n; 5. while (gap > 1) { 6. gap = gap / 3 + 1; 7. for (int i = 0; i < n - gap; i++) { 8. int end = i; 9. int x = a[end + gap]; 10. while (end >= 0) { 11. if (a[end] > x) { 12. a[end + gap] = a[end]; 13. end -= gap; 14. } else { 15. break; 16. } 17. } 18. a[end + gap] = x; 19. } 20. } 21. } 22. 23. int main(void) { 24. int arr[] = {100, 520, 0, 78, 66, 99, 123, 97, 12, 2}; 25. ShellSort(arr, 10); 26. for (int i = 0; i < 10; i++) { 27. printf("%d ", arr[i]); 28. } 29. return 0; 30. }
