开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 8种常见排序算法的Java实现及稳定性分析 -> 正文阅读

[数据结构与算法]8种常见排序算法的Java实现及稳定性分析

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、算法实现

1.冒泡排序

1).将序列中所有的元素两两比较，将最小的放在最前面；
2).将剩余序列中所有的元素两两比较，将最小的放在最前面；
3).重复第二步，直到只剩下一个数。

冒泡排序

代码如下（示例）：

import java.util.Arrays;
public class BubbleSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void bubbleSort(int[] arr) {
        boolean flag = true;
        for(int i = 0; i < arr.length && flag; i++) {
            flag = false;
            for(int j = arr.length - 1; j > i; j--) {
                //升级版的冒泡，最好时间复杂度可以是O(n)
                if(arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = true;
                }
            }
        }
    }
    private static void bubbleSortOld(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = i + 1; j < arr.length; j++) {
                //最基础的冒泡，即使有序，时间复杂度也是O(n2)
                if(arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}

时间复杂度(平均)：O(n2) ? ? 时间复杂度(最好)：O(n) ? ? 时间复杂度(最坏)：O(n2)
空间复杂度：O(1) ? ? ? ? 稳定性：稳定

2.选择排序

1.遍历整个序列，将最小的数放在前面；
2.遍历剩下的序列，将最小的数放在最前面；
3.重复第二步，直到只剩下一个数。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class SelectionSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void selectionSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[min]) min = j;
            }
            if(min != i) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

时间复杂度(平均)：O(n2) ? ? 时间复杂度(最好)：O(n2) ? ? 时间复杂度(最坏)：O(n2)
空间复杂度：O(1) ? ? ? ? 稳定性：不稳定

3.插入排序

1.将第一个元素和第二个元素排序，然后构成一个有序序列；
2.将第三个元素插入进去，构成一个新的有序序列；
3.对第四个元素、第五个元素……直到最后一个数，重复第二步。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class InsertSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void insertionSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
            for(int j = i + 1; j > 0; j--) {
                //如果当前元素比上一个元素小，就交换
                if(arr[j] >= arr[j - 1]) break;
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }
}

时间复杂度(平均)：O(n2) ? ? 时间复杂度(最好)：O(n) ? ? 时间复杂度(最坏)：O(n2)
空间复杂度：O(1) ? ? ? ? 稳定性：稳定

4.希尔排序

1.将元素个数设为n，取奇数k=n/2，将下标差值为k的元素分为一组，构成有序序列；
2.再取k=k/2，将下标差值为k的元素分为一组，构成有序序列；
3.重复第二步，直到k=1执行简单插入排序。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class ShellSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void shellSort(int[] arr) {
        for(int gap = arr.length / 2; gap > 0; gap /= 2) {
            for(int j = 0; (j + gap) < arr.length; j++) {
                for(int k = 0; (k + gap) < arr.length; k += gap) {
                    if(arr[k] > arr[k + gap]) {
                        int temp = arr[k + gap];
                        arr[k + gap] = arr[k];
                        arr[k] = temp;
                    }
                }
            }
        }
    }
}

时间复杂度（平均）：O(n^1.3) ? ? 时间复杂度(最好)：O(n) ? ? 时间复杂度(最坏)：O(n2)
空间复杂度：O(1) ? ? ? ? ???稳定性：不稳定

5.快速排序

1.选择第一个数为p，小于p的放在左边，大于p的数放在右边；
2.递归地将p左边和右边的数都按照第一步进行，直到不能递归。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    private static void quickSort(int[] array, int left, int right) {
        if(left > right) return;
        int i = left, j = right, base = array[left];
        while(i < j) {
            while(i < j && array[j] > base) j--;
            while(i < j && array[i] <= base) i++;
            if(i < j) swap(array, i, j);
        }
        swap(array, i, left);
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

时间复杂度（平均）：O(nlogn) ? ? 时间复杂度(最好)：O(nlogn) ? ? 时间复杂度(最坏)：O(n2)
空间复杂度：O(logn) ? ? ? ? ?? 稳定性：不稳定

6.归并排序

1.选择相邻两个数成为一个有序序列；
2.选择相邻的两个有序序列组成一个有序序列；
3.重复第二步，直到全部成为一个有序序列。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class MergeSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    private static void mergeSort(int[] array, int start, int end) {
        if(start < end) {
            int mid = (start + end) / 2;
            mergeSort(array, start, mid);
            mergeSort(array, mid + 1, end);
            merge(array, start, mid, end);
        }
    }
    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[array.length];
        int p1 = left, p2 = mid + 1, k = left;
        while(p1 <= mid && p2 <= right) {
            if(array[p1] <= array[p2]) temp[k++] = array[p1++];
            else temp[k++] = array[p2++];
        }
        while(p1 <= mid) temp[k++] = array[p1++];
        while(p2 <= right) temp[k++] = array[p2++];
        for(int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
}

时间复杂度（平均）：O(nlogn) ? ? 时间复杂度(最好)：O(nlogn) ? ? 时间复杂度(最坏)：O(nlogn)
空间复杂度：O(n) ? ? ? ???? 稳定性：稳定

7.堆排序

1.将序列构建成大顶堆；
2.将根节点与最后一个节点交换，然后断开最后一个节点；
3.重复第一、第二步，直到所有的节点都断开。

在这里插入图片描述

代码如下（示例）：

import java.util.Arrays;
public class HeapSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        heapSort(array);
        System.out.println(Arrays.toString(array));

    }
    private static void heapSort(int[] array) {
        //1.构建大顶堆
        for(int i = array.length / 2 - 1; i >= 0; i--) {
            //从一个非叶子节点从下至上，从右至左调整结构
            adjustHeap(array, i, array.length);
        }
        //2.交换堆顶元素与末尾元素，并调整堆结构
        for(int j = array.length - 1; j > 0; j--) {
            swap(array, 0, j);
            adjustHeap(array, 0, j);
        }
    }
    private static void adjustHeap(int[] array, int i, int length) {
        int temp = array[i];
        //从i节点的左子节点开始，也就是2i + 1 开始
        for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //如果左子节点小于右子节点，k指向右子节点
            if(k + 1 < length && array[k] < array[k + 1]) k++;
            if(array[k] > temp) { //子节点大于父节点，将子节点赋值给父节点
                array[i] = array[k];
                i = k;
            } else break;;
        }
        array[i] = temp;
    }
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

时间复杂度（平均）：O(nlogn) ? ? 时间复杂度(最好)：O(nlogn) ? ? 时间复杂度(最坏)：O(nlogn)
空间复杂度：O(1) ? ? ? ? ??? 稳定性：不稳定

8.基数排序

1.将所有的数的个位数取出，按照个位数进行排序，构成一个序列；
2.将新构成的所有数的十位数取出，按照十位数进行排序，构成一个序列；
3.重复操作，直至最大位数。

在这里插入图片描述

代码如下（示例）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BasicSortDemo {
    public static void main(String[] args) {
        int[] array = {1, 4, 2, 8, 5, 7, 3, 6, 9, 0};
        System.out.println(Arrays.toString(array));
        basicSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void basicSort(int[] array) {
        List<ArrayList<Integer>> dyadic = new ArrayList<>();
        for(int i = 0; i < 10; i++) {
            ArrayList<Integer> arr = new ArrayList<>();
            dyadic.add(arr);
        }
        int max = 0;
        for (int item : array) {
            if (item > max) max = item;
        }
        int times = 0;//判断最大值为几位数，其位数就是应该循环的次数
        while(max > 0) {
            max /= 10;
            times++;
        }
        for(int i = 0; i < times; i++) {
            for (int value : array) {
                int x = value % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                //将该数组作为下标，找到对应的子数组，将该元素添加到子数组中,并更新大数组
                ArrayList<Integer> arr = dyadic.get(x);
                arr.add(value);
                dyadic.set(x, arr);
            }
        }
        int index = 0; //将子数组依次遍历，将每个子数组中的元素添加到array中
        for(int k = 0; k < 10; k++) {
            while(dyadic.get(k).size() > 0) {
                ArrayList arr = dyadic.get(k);
                array[index] = (int)arr.get(0);
                arr.remove(0);
                index++;
            }
        }
    }
}

时间复杂度（平均）：O(nk) ? ? 时间复杂度(最好)：O(nk) ? ? 时间复杂度(最坏)：O(n*k)
空间复杂度：O(n+k) ? ? ? ? ?稳定性：稳定

二、稳定性分析

排序算法的稳定性：在待排序的序列中，有相同元素，排完序后相同元素的相对位置保持不变，比如在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，这种排序算法就是稳定的。

1.冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。两个元素相等，就不会交换位置了；如果两个相等的元素不相邻，即使两两交换把两个相邻起来，这时候也不会再交换，所以相同元素的前后顺序并没有改变，因此冒泡排序是稳定排序算法。

2.选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推。在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

3.插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

4.希尔排序

希尔排序是按照不同步长对元素进行插入排序。一次插入排序是稳定的，不会改变相同元素的相对顺序，由于有多次插入排序，在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

5.快速排序

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

6.归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个元素(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。在1个不会交换，2个元素如果大小相等也没必要交换，所以不会破坏稳定性。合并过程中我们可以保证如果两个当前元素相等时，把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。因此归并排序也是稳定的排序算法。

7.堆排序

堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。