经典排序算法

选择排序

849589-20171015224719590-1433219824

public static void selectionSort(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }

  // 找出 0 ~ n-1 中的最小值的索引
  // 找出 1 ~ n-1 中的最小值的索引
  // 找出 2 ~ n-1 中的最小值的索引
  // 找出 i ~ n-1 中的最小值的索引
  for (int i = 0; i < arr.length; i++) {
    int minValueIndex = i;
    for (int j = i + 1; j < arr.length; j++) {
      minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
    }
    // 交换值，将每次最小都放入前面
    swap(arr, i, minValueIndex);
  }
}

private static void swap(int[] arr, int i, int j) {
  int iV = arr[i];
  arr[i] = arr[j];
  arr[j] = iV;
}

@Test
public void testSelectionSort() {
  int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
  selectionSort(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度：

两层循环 O(N^2)

冒泡排序

9916080-f0605d250bd43468

依次比较相邻的数，并交换，最后将最大的数冒泡到最后，这样循环 n-1 次后，即可排序所有数。

public static void bubbleSort(int[] arr) {
  if (arr == null || arr.length < 2) {
    return;
  }
  // 0 ~ n-1
  // 0 ~ n-2
  // 0 ~ n-3
  // 0 ~ n-4

  // 也就是 0 ~ end
  for (int end = arr.length - 1; end >= 0; end--) {
    // 在 0 ~ end 上对数进行两两比较，将最大的数冒泡到最后
    // 需要循环 end-1 次，倒数第二次循环已经将最大值选出了
    for (int i = 0; i <= end - 1; i++) { // 从1开始是为了不溢出
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);
      }
    }
  }
}

@Test
public void testBubbleSort() {
  int[] arr = new int[]{1, 3, 5, 3, 2, 9, 2, 5};
  bubbleSort(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度：

1. 假设数组长度为 n，交换方式是最坏的情况，每次都要交换

2. 那么交换次数为： n, n-1, n-2, ... 3, 2, 1

3. 根据等差数列公式，Sn=n*a1+n(n-1)d/2 或者 Sn=n(a1+an)/2，可以得到数据量级n与交换次数之间的关系为 (1/2)*(n^2) -(1/2 -a1)n

4. 保留最高次项，故冒泡排序的时间复杂度为O(n^2)

插入排序

插入排序之所以叫插入排序，是因为他的排序过程类似扑克游戏斗地主的摸牌的排序过程。

849589-20171015225645277-1151100000

public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    // 0 ~ 0 
    // 0 ~ 1 范围有序
    // 0 ~ 2 范围有序
    // ...   
    // 0 ~ n 范围有序
    for (int end = 0; end < arr.length; end++) {
        // 排序新数
        int newNumIndex = end;
        while (newNumIndex - 1 >= 0 && arr[newNumIndex-1] > arr[newNumIndex]) {
            swap(arr, newNumIndex -1, newNumIndex);
            newNumIndex--;
        }
    }
}

时间复杂度：

O(N^2)

归并排序

img

归并排序是时间复杂度为O(n*logn)。

递归实现

1. 让数组arr的L到R位置上有序

2. 将数组拆分为两半，确认中间位置 (L+R)/2 = M

3. 让 L到M， M+1到R范围内有序

4. 左右部分排序成功后，准备一个R-L长度的数组空间，同时遍历左右空间，每次取出一个元素，比较两个两个数字的大小。谁小将谁放额外数组空间中，这样就完成了结果的归并

5. 就这样这样依次对半拆分排序，直到不能再拆分，再依次归并，即可完成归并排序

/**
 * 递归实现归并排序
 */
public void mergeSort1(int[] arr, int L, int R) {
  if (arr == null || arr.length < 2
      || L < 0 || L >= arr.length
      || R < 0 || R >= arr.length || L >= R) {
    return;
  }
  process(arr, L, R);
}

public void process(int[] arr, int L, int R) {
  if (L == R) {
    return;
  }
  int M = (L + R) / 2;
  process(arr, L, M);
  process(arr, M + 1, R);
  merge(arr, L, M, R);
}

public void merge(int[] arr, int L, int M, int R) {
  int[] help = new int[R - L + 1]; // 创建一个用于盛放合并后数组的数组
  int i = 0; // help的指针，每次填充后+1
  int p1 = L; // 遍历左部分的指针
  int p2 = M + 1;// 遍历有部分的指针

  // p1 p2 都在正确的范围内
  while (p1 <= M && p2 <= R) {
    help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
  }

  // 如果p1在正确的范围内，说明p2循环完毕了
  while (p1 <= M) {
    help[i++] = arr[p1++];
  }

  //  如果p2在正确的范围内，说明p1循环完毕了
  while (p2 <= R) {
    help[i++] = arr[p2++];
  }

  // 将help排序后的内容填充到arr中
  for (i = 0; i < help.length; i++) {
    arr[L + i] = help[i];
  }
}

@Test
public void testMergeSort1() {
  int[] arr = new int[]{7, 9, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
  mergeSort1(arr, 0, 5);
  System.out.println(Arrays.toString(arr));
}

复杂度：

T(n) = aT(n/b) + O(N^d)
T(n) = 2T(n/2) + O(N^1)
a = 2, b = 2, d = 1
logbA = 1 == d，那么时间复杂度为  O(N^d * logN) ，即 O(N*logN)

也可以使用for循环替代while：

package com.rhdk.contractservice;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

        // 递归实现归并排序
        int[] arr = new int[]{2, 1, 3, 4};
        mergeSort1(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        sort(arr, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int M = (L + R) / 2;
        sort(arr, L, M);
        sort(arr, M + 1, R);
        merge(arr, L, M, R);
    }

    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int lIndex = L;
        int rIndex = M + 1;

        for (int i = 0; i < help.length; i++) {
            if (lIndex > M && rIndex > R) {
                break;
            }

            if (lIndex > M) {
                help[i] = arr[rIndex++];
                continue;
            }

            if (rIndex > R) {
                help[i] = arr[lIndex++];
                continue;
            }

            if (arr[lIndex] <= arr[rIndex]) {
                help[i] = arr[lIndex++];
            } else {
                help[i] = arr[rIndex++];
            }
        }

        // 填充到原数组
        if (R + 1 - L >= 0) {
            System.arraycopy(help, 0, arr, L, R - L + 1);
        }
    }

}

---

非递归实现

1. 递归是将数组拆分为两半，而这种方式则是将元素分为固定的k组，整体思想是相同的

2. k=1：循环数组，因为数组在[0,0]、[1,1]、[2,2]、[3,3]...范围内有序，合并有序数组，让数组在[0,1]、[2,3]、[4,5]...范围内有序

3. k=2：循环数组，因为数组在[0,1]、[2,3]、[4,5]、[6,7]...范围内有序，合并有序数组，让数组在[0,3]、[4,7]、[8,11]...范围内有序

4. k=4：循环数组，因为数组在[0,3]、[4,7]、[8,11]...范围内有序，合并有序数组，让数组在[0,7]、[8,15]、[16,23]...范围内有序

5. k=?：循环数组，因为数组在[i, i+k-1]范围上有序，合并有序数组，让数组在 [i + 2k-1]范围内有序

6. 如此循环数组，直到k>=arr.length时，即完成了数组的排序

7. 注意边界不能超过数组的长度

8. 如此循环，将2个有序的小组，合并为4个有序的小组

9. 此时让 k=4，按照上述流程继续循环，将4个7有序的小组合并为8个有序的小组

10. 如此反复，

代码如下：

public void mergeSort2(int[] arr) {
  int k = 1;
  int i = 0;
  while (k <= arr.length) {
    if (i >= arr.length) {
      i = 0;
      k <<= 1;
    }
    // 左索引为i，右索引为 i + 2 * k - 1，且不能超过数组长度-1，中间为i + k - 1，且不能超过数组长度
    int L = i;
    int R = Math.min(i + 2 * k - 1, arr.length - 1);
    int M = Math.min(i + k - 1, arr.length - 1);
    // 将小组合并为大组
    merge(arr, L, M, R);
    // 重置i索引
    i += 2 * k;
  }
}

@Test
public void testMergeSort2() {
  int[] arr = new int[]{9, 7, 3, 1, 0, 1, 4, 5, 9, 8, 0, 2};
  mergeSort2(arr);
  System.out.println(Arrays.toString(arr));
}

时间复杂度：

while (k <= arr.length) 
i += 2 * k;
每次使用x2的方式追赶问题规模N，故外层复杂度为 logN

每当if (i >= arr.length) 重新开始循环，这是内层循环
内层循环只走了merge方法，时间复杂度为N

所以时间复杂度也为 O(N * logN)

为什么选择、冒泡、插入排序O(n^2)的时间复杂度劣于归并排序O(N * logN)？

因为前者在比较时，将所有的数依次比较，很多比较行为并没有交换，造成了很多无效的操作。

小和问题

假设有个数组， [6, 3, 4, 6, 7]，

1. 第0个元素左侧比该元素小的值的总和为0

2. 第1个元素左侧比该元素小的值的总和为0

3. 第2个元素左侧比该元素小的值的总和为3

4. 第3个元素左侧比该元素小的值的总和为3+4=7

5. 第4个元素左侧比该元素小的值的总和为6+3+4+6=19

6. 故最小和为 3 + 7 + 19 = 29

要求复杂度为 O(N*logN)

快速排序

快排的步骤：

1. 以数组中最后一个数字P为边界，将数组内的小于等于P的数放在左侧，大于P的数放右侧

2. 当前数 <= P，当前数在 <= 区，当前数与下一个数交换，<= 区扩容1，当前数指针向后移动一次

3. 当前数 > P，当前数指针向后移动