java排序

摘要：本篇blog讨论java实现的各种排序

java排序

引言：十大经典排序

1、冒泡排序

2、插入排序

3、选择排序

4、希尔排序

5、快速排序

6、归并排序

7、桶排序

8、堆排序

9、计数排序

10、基数排序

0、基本概念：

稳定性：如果排序A在B前，如果在排序过程中出现了B在A前的情况，就说该排序不稳定。即使最后可能又恢复成A在前。

以下讨论全部基于增序排序

---

1、冒泡排序：

A：算法概念：每次遍历需要排序的元素集，从前往后依次比较两个相邻元素的大小，如果前面的元素比后面的元素大，就交换两个元素，保证后一个数字更大。

B：核心思想：每趟遍历向相当于把该趟的元素集中最大的元素排到最后。n个元素，只要把n-1个最大的元素放到最后，剩下的一定是最小的。所以需要比较n-1趟。

C：算法步骤：

1. 从头开始，比较相邻的两个数，如果第一个数比第二个数大，那么就交换它们位置。
2. 从开始到最后一对比较完成，一轮结束后，最后一个元素的位置已经确定。
3. 除了最后一个元素以外，前面的所有未排好序的元素重复前面两个步骤。（元素集-1）
4. 重复前面 1 ～ 3 步骤，直到所有元素都已经排好序。

D：注意边界：

• n-1趟（从1开始）
• 第k趟（从1开始）需要比较n-k个元素
• 相等不交换（保证稳定性）

E：代码

public static void bubbleSort(int[] nums){
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < nums.length-i; j++) {
            if(nums[j]>nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

F：性能分析

1. 时间：

   从上面的代码来看，两层 for 循环嵌套，假设数组的大小为 n，那么第一轮冒泡需要比较 n-1 次，第二轮由于最后一个已经排好，需要比较 n-2 次，依次类推下一轮比较 n-3，n-4… 直到最后只需要比较第一个元素和最后一个元素，只有 1 次比较，所以比较次数之和为：
   $$
   1+2+3+…+(n-2)+(n-1)= \frac{n\times(n-1)}{2} = \frac{1}{2}n^2-\frac{1}{2}n
   $$

   上面计算时间复杂度是 $O(n^2)$，时间复杂度取系数最高的项即可，当然这是最坏情况下的时间复杂度。如果这个数组已经排好序了，我们在每一轮冒泡的时候，都增加一个标识，表示是否有交换，如果没有交换，说明数组顺序已经排好，排序提前结束。这样一来，时间复杂度就是 O(n) 了，因为只遍历了第一轮的 n 个数（第一轮遍历完就发现标识没改变，跳出）。

   但是并非所有情况下的排序都这么一帆风顺，除了最好和最坏的情况，还有一些中间情况，平均时间复杂度仍为 $O(n^2)$。

2. 空间：由于只使用了一个中间变量temp，没有借助其他的变量，所以空间复杂度为 O(1)

3. 稳定性：稳定👉只有当前面的元素比后面的元素大时，才会交换。

E：进阶

我们可以在每一轮冒泡的时候，都增加一个标识，表示是否有交换，如果没有交换，说明数组顺序已经排好，排序提前结束。

---

2、选择排序

A：算法概念：每次选择剩下元素集中最小的元素，与当前索引位置元素交换

B：核心思想：每轮都把剩下未排序的元素中最小的选出来，置于首位置

C：算法步骤：

1、从第一个元素开始，遍历其后面的元素，找出其后面比它更小的且最小的元素，若有，则两者交换，保证第一个元素最小

2、第二个元素同理：遍历，找到，交换，确保第二个元素在未排序的数中最小

3、依次类推，直到最后。

D：注意边界：

每一趟排序都能把一个最小的数排到前面，所以只需要$n-1$趟。对于第 $i$ 趟排序，需要比较$n-i$次来获得最小值

E：代码：

public static void Sort(int[] nums){
    for (int i = 0; i < nums.length-1 ; i++) {
        int minIndex = i;
        //最巧妙的是j，我们用j代表待比较元素下标，而不要用j代表次数什么的
        for (int j = i+1; j < nums.length; j++) {
            if(nums[j]<nums[minIndex])
                minIndex = j;
        }
        int t = nums[minIndex];
        nums[minIndex] = nums[i];
        nums[i] = t;
    }
}

F：性能分析

1. 时间

   从上面的代码来看，也是两层 for 循环嵌套，假设数组的大小为 n，那么第一轮选择的数需要 n-1 次，第二次选择由于第一个已经排好，需要比较 n-2 次，依次类推下一轮比较 n-3，n-4 … 直到最后第n-1趟只有 1 次查找，所以比较次数之和为：
   $$
   1+2+3+…+(n-2)+(n-1)= \frac{n\times(n-1)}{2} = \frac{1}{2}n^2-\frac{1}{2}n
   $$

   上面计算时间复杂度是 $O(n^2)$，选择排序没有最好最坏的情况之分，所有情况都需要遍历所有未确定的元素，选择出最小的，所以最好的情况时间复杂度仍然是 $O(n^2)$，平均时间复杂度也是 $O(n^2)$。

   原因是选择排序每趟即使没有发生元素交换，也只能说明剩下的数都比第一个小，但却无法说明相互之间的关系。

2. 空间

   空间复杂度由于只使用了一个变量 minIndex，没有借助其他的变量，所以空间复杂度为 O(1)。

3. 稳定性

   由于选择排序只会选择最小的元素进行交换，如果我们可以保证我们每次选择到的最小元素是第一次出现的（就算后面出现大小相等的元素我们也不会选择后面的），那么就可以保证它的稳定性，所以选择排序是可以做到稳定的。

---

3、插入排序

A：算法概念：

B：核心思想：

C：算法步骤：

1、

D：注意边界：

E：代码

public static void sort(int[] nums){
    for (int i = 1; i < nums.length; i++) {
        int temp = nums[i];
        int index = i-1;
        //关键在于理解index，index表示的是当前元素的前一个位置
        //只要index下标表示的元素存在，且更大，就往后移
        while(index>-1 && nums[index]>temp){{
            nums[index+1] = nums[index];
            index--;
        }
        //最后的index的上一次肯定是满足条件的，即已经被挪到它后面了，即最后的index上一次那个位置是空的，所以要加回来（因为最后减了一次）           
        nums[index+1] = temp;
        }
    }
}

四、希尔排序

E：代码

注：希尔排序的实现还是比较绕的，以下给出了定义实现版本和优化版本

public static void sort(int[] nums){
    //严格按照定义来写
    //经检验，无论数组长度为奇数还是偶数，都是一共有gap组
    //希尔排序无论如何都会经过gap=1这一组,如果数组只有一个数，就不会进入循环体
    for (int gap = nums.length/2; gap>0 ; gap/=2) {
        //按组书写
        for(int i=0;i<gap;i++){
            for (int j = i; j < nums.length; j+=gap) {
                int temp = nums[j];
                int index = j-gap;
                while(index>-1 && nums[index]>temp){
                    nums[index+gap] = nums[index];
                    index -= gap;
                }
                nums[index+gap] = temp;
            }
        }
    }
}

public static void shellSort(int[] nums) {
    for (int gap = nums.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < nums.length; i++) {
            int j = i;
            int temp = nums[j];
            if (nums[j - gap] > nums[j]) {
                while (j - gap >= 0 && temp < nums[j - gap]) {
                    // 移动法
                    nums[j] = nums[j - gap];
                    j -= gap;
                }
                nums[j] = temp;
            }
        }
    }
}

五、快速排序

A：算法概念：每层快排将数组处理成以一个基准数为中心，左边均小于，右边均大于的数组。然后对基准数左边、右边，分别进行快排（分治+递归）

B：核心思想：双指针+分治，每次分成左右两半

C：算法步骤：

1. 从数组中挑一个元素作为基准数，一般情况下我们选择第一个 nums[i]，保存为 standardNum，可以理解为 nums[i] 坑位的数被拎出来了，留下空的坑位。
2. 取数组的左边界索引指针 i，右边界索引指针 j，j 从右边往左边，寻找到比 standardNum 小的数，停下来，写到 nums[i] 的坑位，nums[j] 的坑位空出来。 索引指针i 从左边往右边找，寻找比 standardNum 大的数，停下来，写到 nums[j] 的坑位，这个时候，num[i] 的坑位空出来（前提是 i 和 j 不相撞）。
3. 上面的 i 和 j 循环步骤 2，直到两个索引指针 i 和 j 相撞，将基准值 standardNum 写到坑位 nums[i] 中，这时候，standardNum 左边的数都小于等于它本身，右边的数都大于等于它本身。
4. 分别对 standardNum 左边的子数组和右边的子数组，循环执行前面的 1，2，3，直到不可再分，并且有序。

D：注意边界：

对于任一层快排而言，可能出现两种越界：

左边数组：end-1可能会小于0

右边数组：end+1可能会超出数组长度

两种情况，都可以归结为左大于右

E：代码：

代码经历了一次重构过程，见《重构》

public static void sort(int[] nums,int S, int E){
    if(S>=E)
        return;
    int start = S,end = E,temp = nums[start];
    while(start<end){
        //从后向前
        while(start<end&&nums[end]>=temp)
            end--;
        if(start<end)
            nums[start] = nums[end];
        //从后向前之后，可以直接接上从前向后
        while (start<end&&nums[start]<=temp)
            start++;
        if(start<end)
            nums[end] = nums[start];
    }
    nums[start]=temp;
    sort(nums,S,end-1);
    sort(nums,end+1,E);
}

F：性能分析

• 时间

  每层快排，这n个数一定都走了一遍。复杂度主要取决于递归层数。对于递归层数而言：

  最好的情况是，每次总能五五分，则递归层数是log2n。两者相乘，时间复杂度为nlog2n。

  最坏的情况是，数组原本有序，选择基准之后，左边是 1 个数，右边是 n-1 个数。右边的 n-1 个数，选完基准值，比较完一轮之后，又是左边部分 1 个数，右边部分 n-2 个数，以此递推：
  $$
  1+2+3+…+(n-2)+(n-1)= \frac{n\times(n-1)}{2} = \frac{1}{2}n^2-\frac{1}{2}n
  $$
  平均时间复杂度：nlogn

• 空间

  虽然快排本身没有申请额外的空间，但是递归需要使用栈空间，递归树的深度是 log2n，空间复杂度也就是 log2n。

• 稳定性

  由于快速排序会将一个数从一边移动到一边，大的数放在右边，小的数放在左边，所以会破坏两个相等的元素的相对顺序，所以它是不稳定的排序算法。

赏

谢谢你请我吃糖果