常见排序算法

2020-10-05

× 文章目录

1. 1.冒泡排序
2. 2.选择排序
3. 3.插入排序（劣化版）
4. 4.插入排序（优化版）

本文将主要介绍一些常见的排序算法，使用语法为Java，默认排序方向为从小到大。

1.冒泡排序

原理很简单，直接上代码：

// 冒泡排序
public static void bubbleSort(int[] array) {
    // 1. 每次循环，都能冒泡出剩余元素中最大的元素，因此需要循环 array.length 次
    for (int i = 0; i < array.length; i++) {
        // 2. 每次遍历，只需要遍历 0 到 array.length - i - 1中元素，因此之后的元素都已经是最大的了
        for (int j = 0; j < array.length - i - 1; j++) {
            //3. 交换元素
            if (array[j] > array[j + 1]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

2.选择排序

选择排序的核心思想在于：

利用两个变量,一个存储当前最大值,一个存储当前最大值所在的索引。
依次比较后面的元素,如果发现比当前最大值大,则更新最大值,并且更新最大值所在的索引。
直到遍历结束,将最大值放在数组的最右边,也就是交换最右边元素和当前最大值元素。
重复上面的步骤。

代码实现如下，这里列出两种实现方式，本质是一样的：

//选择排序1
public static void selectSort(int[] array) {
    for(int i=0;i<array.length;i++){
        int max=array[0];
        int index=0;
        for(int j=0;j<array.length-i;j++){
           if(max<array[j]){
                max=array[j];
                index=j;
            }
            if(j==array.length-1-i){
                int temp=array[j];
                array[j]=max;
                array[index]=temp;
            }
        }
   }
}
    
//选择排序2
public static void selectSort2(int[] array) {
  // 遍历N次，每次选择数组剩余元素中最大的元素
  for (int i = 0; i < array.length; i++) {
    // 暂时把第一个元素当做最大元素，并且记录最大元素的索引
    int maxIndex = 0;
    int max = array[0];
    // 注意 j 从 索引1 开始，到 array.length - i 截止
    for (int j = 1; j < array.length - i; j++) {
      // 如果元素大于当前最大值，则替换 max，maxIndex
      if (array[j] > max) {
        max = array[j];
        maxIndex = j;
      }
    }
      
    // 交换最大值元素 和 数组末尾元素
    int temp = array[maxIndex];
    array[maxIndex] = array[array.length - i - 1];
    array[array.length - i - 1] = temp;
  }
}

3.插入排序（劣化版）

本节的插入排序直接选择将倒数第二个元素作为临时元素，核心思想如下：

在第一轮,抽离数组末尾倒数第二个元素,作为临时元素。
用临时元素与数组后面的元素进行对比,如果后面的元素值小于临时元素,则左移。
如果后面的元素大于临时元素,或者已经移动到数组末尾,则将临时元素插入当前的空隙中。
重复上面步骤,完成排序。

代码实现如下，这里列出两种实现方式，其中第一种方式与上述思路有细微差别，在第2,3步的处理上选择通过逐次交换元素的方式达成排序的目的，在时间复杂度上应该要劣于第二种方式：

（好吧其实第一种方式就是我当时自己根据思路写的，第二种方式是标准答案orz，不过我的方法不用考虑移动到尾部的情况，不知道算不算一个小优化？）

// 插入排序1
public static void insertSort(int[] array) {
    for(int i =array.length-2;i>=0;i--){
        //这里的k用于在后期交换元素时控制临时元素的移动，具体实现为：array[i+k]
        int k =0;
        for(int j=1;i+j<array.length;j++){
            if(array[i+k]>array[i+j]){
                int temp = array[i+k];
                array[i+k]=array[i+j];
                array[i+j]=temp;
                k++;
            }
        }
    }
}

// 插入排序2
public static void insertSort2(int[] array) {
    // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
    for (int i = array.length - 2; i >= 0; i--) {
        // 存储当前抽离的元素
        int temp = array[i];
        // 从抽离元素的右侧开始遍历
        int j = i + 1;
        while (j <= array.length - 1) {
            // 如果某个元素，小于临时元素，则这个元素左移
            if (array[j] < temp) {
                array[j - 1] = array[j];
            } else {
                // 如果大于，则直接将临时元素插入，然后退出循环。
                array[j - 1] = temp;
                break;
            }
            j++;
        }

        // 处理到达尾部的情况
        if (j == array.length) {
            array[j - 1] = temp;
        }
    }
}

4.插入排序（优化版）

在上文的劣化版插入排序，相当于是从尾至头遍历了一遍，如果将这种遍历与二分法查找结合，效率将会继续上升。

代码如下：

// 插入排序
public static void insertSort(int[] array) {
    // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
    for (int i = array.length - 2; i >= 0; i--) {
        // 存储当前抽离的元素
        int temp = array[i];
        int index = searchIndex(array, i + 1, array.length - 1, temp);

        // #1. 根据插入的索引位置，进行数组的移动和插入
        int j = i + 1;
        while (j <= index) {
            array[j - 1] = array[j];
            j++;
        }
        array[j - 1] = temp;
    }
}

// 查找应该插入的索引位置
public static int searchIndex(int[] array, int left, int right, int aim) {
    // 循环查找节点位置
    while (left < right) {
        int middle = (left + right) / 2;
        int value = array[middle];
        if (value < aim) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    // #1. 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
    if(array[left] > aim){
        return left -1;
    }
    // 否则就是当前位置
    return left;
}