8种基础排序算法
2021-01-16 / highPhone啊

基础环境准备：创建一个数据大小为n，数值为1000范围内的随机数组，调用排序方法，分别输出排序前和排序后的数组：

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
public static void main(String[] args) {
    int n = 2000;
    int[] array = createRandomArray(n);
    System.out.println("Before Sorted:" + Arrays.toString(array));
    long start = System.currentTimeMillis();
    insertSort(array);
    long end = System.currentTimeMillis();
    System.out.println("Sorted " + n + " nums costs " + (end -start) + "ms");
    System.out.println("After Sorted:" + Arrays.toString(array));
}

/***
 * create an array that contains n integer elements
 * @param n
 * @return int[]
 */
public static int[] createRandomArray(int n)
{
    int[] res = null;
    if(n > 0)
    {
        res = new int[n];
        Random random = new Random();
        for(int i = 0; i < n; i++)
        {
            res[i] = random.nextInt(1000);
        }
    }
    return res;
}

/***
 * 交换数组中下标为i和下标为j的位置
 * @param array
 * @param i
 * @param j
 */
public static void swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

插入排序

基本思想

从数组的第一个元素开始，即下标0开始，维护一个有序序列，从数组第一个元素开始遍历到数组结束，每个元素去前面维护的有序序列中找到自己的正确位置，然后插入有序序列中，外层遍历结束，数组就是有序的了。下图是插入排序动画演示：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//此处实现为由小到大升序排列
public static void insertSort(int[] array) {
    int len = array != null ? array.length : 0;
    if (len > 1) { //数组元素大于一个才有排序的必要
        for (int i = 1; i < len; i++) {
            int temp = array[i];  //待确定插入的元素
            int j = i; //当前有序序列为[0, j-1]
            while (j > 0 && temp < array[j - 1]) {//如果待插入元素比有序列表中的元素小，循环寻找合适的位置，知道找到小于等于待插入元素，或者没有找到(带插入元素为当前有序序列中最小的元素)
                array[j] = array[j - 1];
                j--;
            }
            if (j != i) {//如果j有移动，即需要进行插入操作。
                array[j] = temp;
            }
        }
    }
}

排序效果

2000个值在0～1000之前的随机数组，排序耗时为5ms：

时间复杂度和空间复杂度

  • 空间复杂度
    插入排序空间复杂度是O(1)。
  • 时间复杂度
  1. 在最好情况下，给定待排序数组就是有序的，所以只需要从下标1到n-1遍历一边，此时时间复杂度是O(n-1)即**O(n)**。
  2. 在最坏情况下，给定待排序数组是逆序的，当外层为i是，内层循环需要判断的次数也为i，所以总次数为 1 + 2 + … + n -1 = n * (n-1) / 2 = 0.5(n^2) - 0.5n, 此时时间复杂度是O(n^2)。
  3. 在平均情况下，插入排序的时间复杂度也是O(n^2)，具体计算过程，见如下文章：插入排序——平均算法复杂度分析

冒泡排序

基本思想

冒泡排序需要两层循环，外层循环控制总共需要进行多少次冒泡操作，内层循环则负责进行冒泡: 假设数组长度为n，当前是第i次冒泡操作，则需要在[0,n-1-i)区间内，对相邻的两个元素进行比较，把元素值大的元素放到相邻位置中靠后的位置(冒泡)。下图是冒泡动画演示:

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/***
 * 冒泡排序，从小到大升序排列
 * @param array
 */
public static void bubbleSort(int[] array)
{
    int len = array != null ? array.length : 0;
    if (len > 1) {
        for(int i = 0; i < len - 1; i++) //需要进行的冒泡次数：数组长度 - 1
        {
            for(int j = 0; j < len - 1 - i; j++) //当前冒泡操作需要比较的次数：数组长度 - 1 - i
            {
                if(array[j] > array[j + 1])  //把大的元素放到相邻位置的靠后位置
                {
                    swap(array, j, j + 1);
                }
            }
        }
    }
}

排序效果

2000个值在0～1000之前的随机数组，排序耗时为9ms：

时间复杂度和空间复杂度

  • 空间复杂度
    冒泡排序空间复杂度是O(1)。
  • 时间复杂度
  1. 在最好情况下，给定待排序数组就是有序的，外层循环次数是n-1次，内层循环仍然需要对相邻元素做比较判断，所以时间复杂度是 n - 1 + n-2 + … + 1 = n * (n-1) / 2 = 0.5(n^2) - 0.5n, 此时时间复杂度是O(n^2)。
  2. 在最坏情况下，给定待排序数组是逆序的，此时循环的次数跟最好情况下是一样的，但此时内层循环除了要进行比较还要进行交换操作，所以耗时会比最好情况下多一些，但时间复杂度量级仍然是O(n^2)。
  3. 由上可知，在平均情况下，冒泡算法的时间复杂度也是O(n^2)。

选择排序

基本思想

选择排序也是需要两层循环，外层循环控制选择操作的次数，内层循环中寻找第i次选择的元素，即第i小的元素。如果数组长度为n，外层循环遍历到第i次，内层循环选择操作需要遍历的次数为n - i - i。下图是选择排序动画演示：

代码实现

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 selectionSort(int[] array)
{
    int len = array != null ? array.length : 0;
    if (len > 1) {
        for(int i = 0; i < len - 1; i++)
        {
            int min = i;
            for(int j = i + 1; j < len; j++)
            {
                if(array[j] < array[min])
                {
                    min = j;
                }
            }
            if(min != i)
            {
                swap(array, i, min);
            }
        }
    }
}

排序效果

2000个值在0～1000之前的随机数组，排序耗时为8ms：

时间复杂度和空间复杂度

  • 空间复杂度
    选择排序空间复杂度是O(1)。
  • 时间复杂度
  1. 在最好情况下，给定待排序数组就是有序的，外层循环次数是n-1次，内层循环进行选择的时候仍然需要进行判断，所以时间复杂度是 n - 2 + n-3 + … + 1 = (n - 1) * (n-2) / 2 = 0.5(n^2) - 1.5n + 1, 此时时间复杂度是O(n^2)。
  2. 在最坏情况下，给定待排序数组是逆序的，此时循环的次数跟最好情况下是一样的,所以此时时间复杂度仍然是O(n^2)。
  3. 由上可知，在平均情况下，选择排序算法的时间复杂度也是O(n^2)。

快速排序

基本思想

  1. 快速排序通常需要设定一个基准数，以基准数来遍历数组，把所有大于基准数的数组元素放在基准数右边，所有小于基准数的数组元素放在基准数左边，这样，以基准数为中心，把数组分成了左半边和右半边两部分数组(分而治之思想)。
  2. 再利用递归思想，分别把左边和右边两部分分别再重复步骤一。
    算法步骤如下图:

代码实现

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
/***
 * 快速排序，二分思想&递归
 * @param array
 * @param left
 * @param right
 */
public static void quickSort(int[] array, int left, int right)
{
    int len = array != null ? array.length : 0;
    if (len > 1 && left < right) //数组长度 > 1 & 左边界小于右边界 
    {
        int temp = array[left];  //基准数
        int i = left;
        int j = right;
        while (i < j)//遍历寻找，把所有比基准数大的数放回右边，所有比基准数小的数放回左边
        {
           while (array[j] >= temp && i < j)//寻找比基准数小的数
               j--;
           while(array[i] <= temp && i < j) //寻找比基准数大的数
               i++;

           if(i < j)  //如果比基准数大的数在左边，比基准数小的数在右边，交换位置
           {
               swap(array, i, j);
           }
        }
        swap(array, left, i); //把基准数放到数组中间
        quickSort(array, left, i - 1); //递归处理左区间
        quickSort(array, i + 1, right);//递归处理右区间
    }
}

排序效果

2000个值在0～1000之前的随机数组，排序耗时为1ms：

时间复杂度和空间复杂度

快速排序的空间复杂度与时间复杂度归纳过程涉及到更多的数学知识，这里不做详尽展开，具体可参考博文快速排序最好，最坏，平均复杂度分析

  • 空间复杂度
    快速排序空间复杂度与其递归深度有关，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
  • 时间复杂度
  1. 在最好情况下，快速排序算法的时间复杂度为O(nlogn)。
  2. 在最坏的情况下，其时间复杂度为O(n^2)。
  3. 在平均情况下，其时间复杂度为O(nlogn)。

未完待续

本文链接：https://highphone.xyz/87dda92b.html