排序算法

1、排序算法

1.1、冒泡排序

1.冒泡排序详细过程

假设原始数组顺序：10, 4, 20, 25, 3

  • 第1轮后的顺序(确定了最大的一个数)：4, 10, 20, 3, (25)
  • 第2轮后的数组(确定了最大的俩个数)：4, 10, 3, (20, 25)
  • 第3轮后的数组(确定了最大的三个数)：4, 3, (10, 20, 25)
  • 第4轮后的数组(确定了最大的四个数)：3, (4, 10, 20, 25)

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
  * 冒泡排序(未优化)
  * @param array
  */
public static void bubbleSort(int[] array) {
    int temp = 0;
    //数组长度为length，则需要排序length - 1轮
    for (int i = 0; i < array.length - 1; i++) {
        //每一轮都从第一个元素开始，一直比到已经排完序的元素的前一个位置再停止，
        //第一轮排完一个最大的，第二轮两个，因此第i轮是length - i - 1
        for (int j = 0; j < array.length - 1 - i; j++) {
            //每两个元素比较，如果前面大于后面，换位
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        System.out.println("冒泡排序第" + (i + 1) + "趟后的数组：" + Arrays.toString(array));
    }
}

//运行结果：
//冒泡排序第1趟后的数组：[4, 10, 20, 3, 25]
//冒泡排序第2趟后的数组：[4, 10, 3, 20, 25]
//冒泡排序第3趟后的数组：[4, 3, 10, 20, 25]
//冒泡排序第4趟后的数组：[3, 4, 10, 20, 25]

2.1 冒泡排序优化

  • 当数组原来就有序，或者排序到一半就已经有序，冒泡排序仍会浪费时间继续两两进行比较，因此，需要定义一个标识，来判断数组是否已经有序，有序的话程序直接结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 冒泡排序优化，原始数组越有序，优化越大
 * @param array
 */
public static void betterBubbleSort(int[] array) {
    int temp = 0;
    boolean flag = false;//标识变量，表示是否进行过交换
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                flag = true; //进入if里面表示交换过
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        System.out.println("冒泡排序第" + (i + 1) + "趟后的数组：" + Arrays.toString(array));
        if (!flag) {
            break; //表示在一趟排序中，未发生过交换，则排序已经完成，结束循环
        } else {
            flag = false; //否则，重置flag，进行下一趟排序
        }
    }
}

/*
	以数组{10, 1, 2, 3, 4, 5}为例：

	优化后的冒泡排序运行结果(仅排了两轮)：
	冒泡排序第1趟后的数组：[1, 2, 3, 4, 5, 10]
	冒泡排序第2趟后的数组：[1, 2, 3, 4, 5, 10]
	未优化的冒泡排序：
	冒泡排序第1趟后的数组：[1, 2, 3, 4, 5, 10]
	冒泡排序第2趟后的数组：[1, 2, 3, 4, 5, 10]
	冒泡排序第3趟后的数组：[1, 2, 3, 4, 5, 10]
	冒泡排序第4趟后的数组：[1, 2, 3, 4, 5, 10]
	冒泡排序第5趟后的数组：[1, 2, 3, 4, 5, 10]
	*/

3.时间复杂度感受

排序十万个随机数所花费时间：15424毫秒，大概15秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    BubbleSort.bubbleSort(a);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

1.2、选择排序

1.选择排序详细过程

假设原始数组顺序：10, 4, 20, 25, 3

  • 第1轮(看全部的数字，将最小的和”第一位”交换顺序)：[10, 4, 20, 25, 3] –> [3, 4, 20, 25, 10]
  • 第2轮(只看后面四个，将最小的和”第一位”交换顺序)：3, [4, 20, 25, 10] –> 3, [4, 20, 25, 10]
  • 第3轮(只看后面三个，将最小的和”第一位”交换顺序)：3, 4, [20, 25, 10] –> 3, 4, [10, 25, 20]
  • 第4轮(只看后面两个，将最小的和”第一位”交换顺序)：3, 4, 10, [25, 20] –> 3, 4, 10, [20, 25]

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 选择排序
 * @param array
 */
public static void selectSort(int[] array) {
    int temp = 0;
    int minIndex; //用于存储最小值的下标
    //数组长度为1，不需要排序；长度为2，需要排1轮...因此选择排序一共需要排length - 1轮
    for (int i = 0; i < array.length - 1; i++) {
        minIndex = i;
        //从第i+1个元素开始找后面的最小值，因为前面的元素已经在前几轮排成有序了
        for (int j = i + 1; j < array.length; j++) {
            //如果遍历到的数比minIndex的那个数还小，那么将这个数下标赋给minIndex
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        //如果这个数不是自己本身，那么和"第一个数"交换，否则不动
        if (minIndex != i) {
            temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
        System.out.println("第" + (i + 1) + "轮排序后的数组：" + Arrays.toString(array));
    }
}

//运行结果：
//第1轮排序后的数组：[3, 4, 20, 25, 10]
//第2轮排序后的数组：[3, 4, 20, 25, 10]
//第3轮排序后的数组：[3, 4, 10, 25, 20]
//第4轮排序后的数组：[3, 4, 10, 20, 25]

3.时间复杂度感受

排序十万个随机数所花费时间：5256毫秒，大概5秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    SelectSort.selectSort(a);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

1.3、插入排序

1.插入排序详细过程

假设原始数组顺序：10, 4, 20, 25, 3

思路：将数组分为 有序表 和 无序表 两部分。之后将无序表的数据取出来插入到有序表的适当位置

  • 有序——————————无序
  • 排序前：(10)——————[4, 20, 25, 3]
  • 第一轮：(4, 10)—————[20, 25, 3]
  • 第二轮：(4, 10, 20)——— [25, 3]
  • 第三轮：(4, 10, 20, 25)——[3]
  • 第四轮：(3, 4, 10, 20, 25)—[]

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 插入排序
 * @param array
 */
public static void insertSort(int[] array) {
    int insertVal;//要插入的元素
    int temp;//要插入的元素的前一个元素下标，此元素及之前的元素都是有序的
    //从第二个元素开始，依次取出插入
    for (int i = 1; i < array.length; i++) {
        insertVal = array[i];
        temp = i - 1;
        //找应该插入的位置，从标记的元素开始向前遍历，一直遍历到第一个(temp<0)，
        //期间不断比较要插入的元素和前一个元素的大小，如果比要插入的元素大，那么大的那个向后移动，空出前面的位置
        //直到某个位置的元素小于要插入的那个元素，则将要插入的元素插入到那个小的元素的后面
        while (temp >= 0 && insertVal < array[temp]) {
            array[temp + 1] = array[temp]; //后移的过程
            temp--; //不断向前移动，循环比较
        }
        array[temp + 1] = insertVal;//需要插入的元素插入到那个小的元素的后面

        System.out.println("插入排序第" + i + "趟后的数组：" + Arrays.toString(array));
    }
}

//运行结果：
//插入排序第1趟后的数组：[4, 10, 20, 25, 3]
//插入排序第2趟后的数组：[4, 10, 20, 25, 3]
//插入排序第3趟后的数组：[4, 10, 20, 25, 3]
//插入排序第4趟后的数组：[3, 4, 10, 20, 25]

3.时间复杂度感受

排序十万个随机数所花费时间：828毫秒，大概0.8秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    InsertSort.insertSort(a);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

1.4、希尔排序

1.希尔排序详细过程

希尔排序VS插入排序

  • 希尔排序其实质是一种特殊的插入排序，插入排序将一个数字插入到有序表里面时，需要将插入的位置之后的数字全部向后移动，这种频繁赋值需要耗费大量时间。
  • 假设一个长度为十万的数组，最小的值恰好在最后一个，那么最后一次插入，前面的九万九个数字全部需要向后移动，每次移动都需要赋值一次，时间太长。
  • 因此，希尔排序为了解决上述问题，其采了分组插入排序的方式(如上图)，当排到最后一次时，数组总体已经趋向由小到大排列，不存在最后一个数还在最后一个的情况，最后一轮也只需要移动几次便可以结束排序，大大提高了排序效率。

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 希尔排序
 * @param array
 */
public static void shellSort2(int[] array) {
    //分组，每隔数组length/2的数为一组，每轮都除2，因此第一轮length/2组，第二轮length/2/2组.....
    for (int step = array.length / 2; step > 0; step /= 2) {
        //下面的步骤本质就是插入排序，只不过是隔开进行
        for (int i = step; i < array.length; i++) {
            int j = i;
            int temp = array[j];
            while (j - step >= 0 && temp < array[j - step]) {
                array[j] = array[j - step];
                j -= step;
            }
            array[j] = temp;
        }
        System.out.println(Arrays.toString(array));
    }
}

//运行结果：
//第1轮排序后的数组：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
//第2轮排序后的数组：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
//第3轮排序后的数组：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3.时间复杂度感受

排序十万个随机数所花费时间：19毫秒，大概0.02秒
排序一百万个随机数所花费时间：182毫秒，大概0.18秒
排序一千万个随机数所花费时间：2517毫秒，大概2.5秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    ShellSort.shellSort2(a);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

1.5、快速排序

1.快速排序详细过程

基本思想：随便找一个数（一般是第一个）作为基准，定义一个左索引，一个右索引；左索引不断向右移，直到找到一个比基准大的数停下，右索引不断向左移，直到找到比索引小的数停下，左右索引所在的两个数交换位置，交换完成，两索引继续按照上面的规则移动，直到左右索引相遇，然后基准数和索引相遇时所在位置的数交换位置，这样一来，基准左边的数都比它小，右边的数都比它大。随后进行左递归、右递归。递归完成，排序完成。

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 快速排序(递归思想)
 * 初始数组：{12, 1, 38, 143, 11, 432, 23, 52}
 */
public static void quickSort(int[] array, int start, int end) {
    //start大于end，直接结束
    if (start >= end) {
        return;
    }
    int left = start; //左索引
    int right = end; //右索引
    int key = array[left]; //基准数
    int temp;
    //当左索引小于右索引，即没有相遇时
    while (left < right) {
        //当索引未相遇，且右索引所在位置的值大于基准，右索引向左移
        while (left < right && array[right] >= key) {
            right--;
        }
        //当索引未相遇，且左索引所在位置的值小于基准，左索引向右移
        while (left < right && array[left] <= key) {
            left++;
        }
        //当上面两个while都退出时，说明右索引找到比基准小的数，左索引找到比基准大的数
        //此时，交换两个数位置，交换完后，若左右索引没有相遇，仍然跳不出大的while循环，会
        //继续执行上面两个循环，即左右索引仍会移动下去
        if (left<right){
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }
    //跳出大的while循环时，代表左右索引已经相遇，此时将两索引所在位置的那个数和基准数交换
    temp = array[left];
    array[left] = array[start];
    array[start] = temp;
    //左递归
    quickSort(array, start, left - 1);
    //右递归
    quickSort(array, right + 1, end);
}

//运行结果：
//排序前：[12, 1, 38, 143, 11, 432, 23, 52]
//排序后：[1, 11, 12, 23, 38, 52, 143, 432]

3.时间复杂度感受

排序十万个随机数所花费时间：26毫秒，大概0.03秒
排序一百万个随机数所花费时间：122毫秒，大概0.12秒
排序一千万个随机数所花费时间：1216毫秒，大概1.2秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    QuickSort.quickSort(a, 0, a.length - 1);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}

1.6、归并排序

1.归并排序详细过程

基本思想：采用分治思想。

  1. 以中间的数为基准，进行左右递归拆分，最后会拆到单个数，下面弹栈时两个组的数字进行组合的同时进行排序。
  2. 定义左右索引，且开辟一个临时数组，长度和原数组相同。左索引指向左数组的开头，右索引指向右数组的开头。
  3. 然后比较两索引所在位置哪个数更小，
    若左索引的那个数更小，则拿出放入临时数组，且左索引向右移动一位，右索引不变，继续比较两数大小；
    若右索引的那个更小，则拿出放到临时数组，且右索引向右移动一位，左索引不变，继续比较两数大小。
  4. 若干次后，有一方会先到数组的尾部，那么两边比较结束，另一方直接将剩下的数按序全部放入临时数组即可。
  5. 最后将临时数组的数据再复制给原数组。
    直到弹栈结束，则排序结束。

2.Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 归并排序
 */
public static void mergeSort(int[] array, int start, int end, int[] temp) {
    if (start < end) {
        int mid = (start + end) / 2;
        //向左递归拆分
        mergeSort(array, start, mid, temp);
        //向右递归拆分
        mergeSort(array, mid + 1, end, temp);
        //合，且排序
        merge(array, start, mid, end, temp);
    }
}

/**
* 合的过程
*/
public static void merge(int[] array, int start, int mid, int end, int[] temp) {
    int left = start; //左数组的索引
    int right = mid + 1; //右数组的索引
    int t = 0; //临时数组temp的下标
    //当左右数组其中一方检索完毕，while循环才会停下
    while (left <= mid && right <= end) {
        //比较左右两边哪个数小，小的那个存入临时数组temp，并将索引后移
        if (array[left] <= array[right]) {
            temp[t] = array[left];
            left++;
        } else {
            temp[t] = array[right];
            right++;
        }
        t++;
    }
    //右数组先比较完，就将左数组剩下的有序数存入temp
    while (left <= mid) {
        temp[t] = array[left];
        left++;
        t++;
    }
    //左数组先比较完，就将右数组剩下的有序数存入temp
    while (right <= end) {
        temp[t] = array[right];
        right++;
        t++;
    }
    //最后将temp里面的有序数组复制进原始数组
    t = 0;
    while (start <= end) {
        array[start] = temp[t];
        t++;
        start++;
    }
}

3.时间复杂度感受

排序十万个随机数所花费时间：16毫秒，大概0.02秒
排序一百万个随机数所花费时间：135毫秒，大概0.13秒
排序一千万个随机数所花费时间：1406毫秒，大概1.4秒

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    int[] a = new int[100000];
    for (int i = 0; i < 100000; i++) {
        a[i] = (int) (Math.random() * 100000);
    }
    long start = System.currentTimeMillis();
    MergeSort.mergeSort(a, 0, a.length - 1, temp);
    long end = System.currentTimeMillis();
    System.out.println(end - start);
}