[关闭]
@natsumi 2017-04-03T08:33:40.000000Z 字数 3247 阅读 818

排序算法们~

Algorithms


1. 交换排序

1.1 冒泡排序

  1. public static void bubbleSort(int[] data) {
  2. for (int i = data.length - 1; i > 0; i--) {
  3. for (int j = 0; j < i; j++) {
  4. if (data[j] > data[j + 1]) {
  5. int temp = data[j];
  6. data[j] = data[j + 1];
  7. data[j + 1] = temp;
  8. }
  9. }
  10. }
  11. }

1.2 快速排序

  1. public static void quickSort(int[] data, int start, int end) {
  2. if (start < end) {
  3. int index = quickSortPartition(data, start, end);
  4. quickSort(data, start, index - 1);
  5. quickSort(data, index + 1, end);
  6. }
  7. }
  8. public static int quickSortPartition(int data[], int start, int end) {
  9. //选取第一个数做轴值,也可以随机选一个
  10. int pivot = data[start];//记录轴值
  11. int i = start;
  12. int j = end;
  13. while (i < j) {
  14. while (i < j && data[j] >= pivot) {//右侧扫描,i所指位置应该是轴值
  15. j--;
  16. }
  17. data[i] = data[j];
  18. while (i < j && data[i] <= pivot) {//左侧扫描,j所指位置应该是轴值
  19. i++;
  20. }
  21. data[j] = data[i];
  22. }
  23. data[i] = pivot;
  24. return i;
  25. }

2. 插入排序

2.1 直接插入排序

  1. public static void insertSort(int[] data) {
  2. for (int i = 1; i < data.length; i++) {//i是无序区的起始位置,第i个元素是待插入元素,i前面是有序区
  3. int toInsert = data[i];
  4. int j = i - 1;
  5. for (; j >= 0 && data[j] > toInsert; j--) {
  6. data[j + 1] = data[j];
  7. }
  8. data[j + 1] = toInsert;
  9. }
  10. }

2.2 希尔排序

  1. public static void ShellInsertSort(int data[]) {
  2. for (int d = data.length >> 1; d >= 1; d >>= 1) {//d是每趟排序的增量
  3. for (int i = d; i < data.length; i++) {//i表示待插入的元素
  4. if (data[i] < data[i - d]) {
  5. int j = i - d, toInsert = data[i];
  6. //以d为间隔找到i前面以d为增量的有序区内的插入位置
  7. for (; j >= 0 && toInsert < data[j]; j -= d) {
  8. data[j + d] = data[j];
  9. }
  10. data[j + d] = toInsert;
  11. }
  12. }
  13. }
  14. }

3. 选择排序

3.1 选择排序

  1. /**
  2. * 选择排序(不稳定),时间复杂度O(n^2),空间O(1)
  3. * <p>
  4. * 举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会
  5. * 和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排
  6. * 序不是一个稳定的排序算法
  7. */
  8. public static void selectSort(int[] data) {
  9. //position用来记录剩下元素最小值的下标
  10. for (int i = 0; i < data.length - 1; i++) {//i表示无序区的开始
  11. //min用来记录最小值,minIndex用来记录最小值下标
  12. int minIndex = i;
  13. int min = data[i];
  14. for (int j = i + 1; j < data.length; j++) {//循环找到无序区的最小值
  15. if (data[j] < min) {
  16. minIndex = j;
  17. min = data[j];
  18. }
  19. }
  20. if (minIndex != i) {//如果无序区最小值不是无序区的第一个元素
  21. //将无序区最小值和无序区第一个元素交换
  22. data[minIndex] = data[i];
  23. data[i] = min;
  24. }
  25. }
  26. }

3.2 堆排序

  1. /**
  2. * 用小根堆实现从大到小排序
  3. *
  4. * @param data 待排序数组
  5. */
  6. public static void heapSort(int[] data) {
  7. for (int i = data.length / 2 - 1; i >= 0; i--) {
  8. sift(data, i, data.length);
  9. }
  10. for (int i = 0; i < data.length - 1; i++) {
  11. int tmp = data[0];
  12. data[0] = data[data.length - 1 - i];
  13. data[data.length - i - 1] = tmp;
  14. sift(data, 0, data.length - i - 1);
  15. }
  16. }
  17. /**
  18. * 小根堆的筛选
  19. *
  20. * @param data 小根堆数组
  21. * @param i 待筛选节点下标
  22. * @param size 堆的节点个数,data[0]-data[size-1]是堆的节点
  23. */
  24. public static void sift(int data[], int i, int size) {
  25. int j = (i << 1) + 1;//j是i的左孩子
  26. int tmp = data[i];//记录节点i的数值
  27. while (j < size) {
  28. if (j + 1 < size && data[j] > data[j + 1]) j++;//j是左右孩子中的较小者
  29. if (tmp < data[j]) break;//符合小根堆条件不需要调整
  30. //不符合小根堆条件“交换”节点i和节点j值
  31. data[i] = data[j];
  32. //更新i,下次循环中再对i进行筛选
  33. i = j;
  34. j = (i << 1) + 1;
  35. }
  36. data[i] = tmp;
  37. }

4. 归并排序

4.1 归并排序

  1. public static void mergeSort(int[] data) {
  2. mergeSort(data, 0, data.length - 1);
  3. }
  4. public static void mergeSort(int[] data, int left, int right) {
  5. if (left >= right)
  6. return;
  7. // 找出中间索引
  8. int center = (left + right) / 2;
  9. // 对左边数组进行递归
  10. mergeSort(data, left, center);
  11. // 对右边数组进行递归
  12. mergeSort(data, center + 1, right);
  13. // 合并
  14. merge(data, left, center, right);
  15. }
  16. /**
  17. * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序
  18. *
  19. * @param data 数组对象
  20. * @param left 左数组的第一个元素的索引
  21. * @param center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
  22. * @param right 右数组最后一个元素的索引
  23. */
  24. public static void merge(int[] data, int left, int center, int right) {
  25. int[] tmpArr = new int[data.length];// 临时数组
  26. int p1 = left;// 左数组第一个元素的索引
  27. int p2 = center + 1;// 右数组第一个元素索引
  28. int i = left;// i 记录临时数组的索引
  29. while (p1 <= center && p2 <= right) {
  30. // 从两个数组中取出最小的放入临时数组
  31. if (data[p1] <= data[p2]) {
  32. tmpArr[i++] = data[p1++];
  33. } else {
  34. tmpArr[i++] = data[p2++];
  35. }
  36. }
  37. // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)
  38. while (p2 <= right) {
  39. tmpArr[i++] = data[p2++];
  40. }
  41. while (p1 <= center) {
  42. tmpArr[i++] = data[p1++];
  43. }
  44. // 将临时数组中的内容拷贝回原数组中
  45. // (原left-right范围的内容被复制回原数组)
  46. for (p1 = left; p1 <= right; p1++) {
  47. data[p1] = tmpArr[p1];
  48. }
  49. }

5. 分配排序

???

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