[关闭]
@Yano 2017-08-06T08:43:06.000000Z 字数 3088 阅读 1398

Java 八大排序实现

Java


参考链接

本文只给出算法的Java实现版本,具体原理参考:八大排序算法

公用代码

下面的swap()函数,是排序算法中经常用到的,单独贴出来。

  1. public void swap(int[] a, int i, int j) {
  2. int tmp = a[i];
  3. a[i] = a[j];
  4. a[j] = tmp;
  5. }

冒泡排序

  1. /**
  2. * 冒泡排序:每次循环,将最后一个位置排序好
  3. * 算法改进:加一个标志位,记录每趟排序最后一个进行交换的位置,下一次只需扫描到pos
  4. * @param a
  5. */
  6. public void bubbleSort(int[] a) {
  7. if (a == null) {
  8. return;
  9. }
  10. int right = a.length - 1;
  11. while (right > 0) {
  12. int pos = 0;
  13. for (int start = 0; start < right; start++) {
  14. if (a[start] > a[start + 1]) {
  15. swap(a, start, start + 1);
  16. pos = start;
  17. }
  18. }
  19. right = pos;
  20. }
  21. }

直接插入排序

将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

  1. public void insertSort(int[] a) {
  2. for (int right = 1; right < a.length; right++) {
  3. if (a[right] < a[right - 1]) {
  4. int tmp = a[right]; // 保存临时变量
  5. int left = right - 1;
  6. a[right] = a[right - 1]; // 先后移一个位置
  7. for (; left >= 0 && tmp < a[left]; left--) {
  8. a[left + 1] = a[left];
  9. }
  10. a[left + 1] = tmp;// 插入到正确位置
  11. }
  12. }
  13. }

简单选择排序

  1. 选出最小的元素,与数组第一个位置交换
  2. 选出第i小的元素,与数组第i个位置交换
  3. 直到第n-1个元素,与第n个元素比较为止
  1. /**
  2. * 选择排序-简单选择排序
  3. * 基本思想:在一组要排序的数中,选取最小的与第一个位置交换
  4. */
  5. public void selectSort(int[] a) {
  6. for(int start = 0; start < a.length; start++) {
  7. int key = selectMinKey(a, start);
  8. swap(a, key, start);
  9. }
  10. }
  11. private int selectMinKey(int[] a, int start) {
  12. int key = start;
  13. for(int i = start; i < a.length; i++) {
  14. key = a[key] > a[i] ? i : key;
  15. }
  16. return key;
  17. }

快速排序

  1. public void quickSort(int[] a) {
  2. quickSort0(a, 0, a.length - 1);
  3. }
  4. private void quickSort0(int[] a, int low, int high) {
  5. if (low < high) {
  6. int pos = partition(a, low, high);
  7. quickSort0(a, low, pos - 1);
  8. quickSort0(a, pos + 1, high);
  9. }
  10. }
  11. private int partition(int[] a, int low, int high) {
  12. int privotKey = a[low];
  13. while (low < high) {
  14. while (low < high && a[high] >= privotKey) {
  15. high--;
  16. }
  17. swap(a, low, high);
  18. while (low < high && a[low] <= privotKey) {
  19. low++;
  20. }
  21. swap(a, low, high);
  22. }
  23. return low;
  24. }

归并排序

  1. public void mergeSort(int[] a) {
  2. mergeSort0(a, 0, a.length - 1);
  3. }
  4. private void mergeSort0(int[] a, int left, int right) {
  5. if (left < right) {
  6. int mid = (left + right) / 2;
  7. mergeSort0(a, left, mid);
  8. mergeSort0(a, mid + 1, right);
  9. merge(a, left, mid, right);
  10. }
  11. }
  12. private void merge(int[] a, int start1, int mid, int right) {
  13. int[] tmp = new int[a.length];
  14. int k = start1; // tmp的初始下标
  15. int start = start1; // 记录初始位置
  16. int start2 = mid + 1; // 第2个数组的起始位置
  17. for(; start1 <= mid && start2 <= right; k++) {
  18. tmp[k] = a[start1] < a[start2] ? a[start1++] : a[start2++];
  19. }
  20. // 左边剩余的合并
  21. while (start1 <= mid) {
  22. tmp[k++] = a[start1++];
  23. }
  24. // 右边剩余的合并
  25. while (start2 <= right) {
  26. tmp[k++] = a[start2++];
  27. }
  28. // 复制数组
  29. while (start <= right) {
  30. a[start] = tmp[start];
  31. start++;
  32. }
  33. }

堆排序

  1. public void heapSort(int[] a) {
  2. buildingHeap(a, a.length);
  3. for (int i = a.length - 1; i > 0; i--) {
  4. swap(a, i, 0);
  5. adjustHeap(a, 0, i);
  6. System.out.println(Arrays.toString(a));
  7. }
  8. }
  9. /**
  10. * 选择排序-堆排序
  11. *
  12. * 若以一维数组存储一个堆,则堆对应一个完全二叉树,且所有非叶结点的值,不大于其子女的值
  13. * 堆顶元素是最小的(小顶堆)
  14. *
  15. *
  16. * 已知a[s...m]除了a[s]外均满足堆的定义 调整a[s],使之成为大顶堆,将第s个结点为根的子树筛选
  17. *
  18. * a:待调整的堆数组 s:待调整的数组元素的位置 length:数组长度
  19. */
  20. private void adjustHeap(int[] a, int s, int length) {
  21. int tmp = a[s];
  22. int child = 2 * s + 1; // 左孩子结点位置
  23. while (child < length) {
  24. // 如果有右孩子,同时右孩子值 > 左孩子值
  25. if (child + 1 < length && a[child] < a[child + 1])
  26. child++;
  27. if (a[s] < a[child]) { // 较大的子结点>父节点
  28. a[s] = a[child]; // 替换父节点
  29. s = child; // 重新设置,待调整的下一个结点位置
  30. child = 2 * s + 1;
  31. } else
  32. break;
  33. a[s] = tmp; // 交换
  34. }
  35. }
  36. /**
  37. * 初始堆进行调整 将a[0...length-1]建成堆
  38. * 调整完后,第一个元素是序列最小的元素
  39. */
  40. private void buildingHeap(int[] a, int length) {
  41. // 最有一个有孩子结点的位置是 i = (length - 1) / 2
  42. for (int i = (length - 1) / 2; i >= 0; i--) {
  43. adjustHeap(a, i, length);
  44. }
  45. }

测试用例

  1. @Test
  2. public void testHeapSort() {
  3. int[] a = new int[] { 4, 11, 5, 8, 1, 9, 2 };
  4. heapSort(a);
  5. System.out.println(Arrays.toString(a));
  6. }

图解

buildingHeap 后,形成了大顶堆。

已经找到最大元素,与数组最后一个位置交换。

交换之后的二叉树并不平衡,需要调整。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注