[数据结构与算法] 数据结构排序算法总结比较

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

-> 数据结构与算法 -> 数据结构排序算法总结比较 -> 正文阅读

[数据结构与算法]数据结构排序算法总结比较

排序算法详解

1.直接插入排序

算法思想·：

把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，与有序表中的元素进行比较，将它插入到有序表中的适当位置，使之成为新的有序表，直到所有的元素都插入到有序表中。

代码实现：

//直接插入排序
    public static void DirectInsert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];//记录当前要插入的数
            int index = i-1;//记录需要插入到的位置 初值为有序表表尾index

            //将满足插入条件的数插入到正确的位置
            while(index >= 0 && cur < arr[index] ){
                arr[index + 1] = arr[index];
                index--;
            }
            //排除cur已经有序的情况
            if(index + 1 != i){
                //插入到有序表中
                arr[index + 1] = cur;
            }
        }
    }

时间复杂度：

最好情况 O(n) 最坏情况 O(n^2) 平均情况 O(n^2)

空间复杂度：

只需要一个辅助空间cur 保存插入的数值 O(1)

优缺点

优点：易于理解便于实现是稳定排序
缺点：在初始值无序数据量大的时候时间复杂度较高

2.折半插入排序

算法思想·：

与直接插入排序思想基本一致，只是再插入数据的时候使用了折半查找的思想去定位插入的下标

代码实现：

//折半插入排序
    public static void BinInsert(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];//记录当前要插入的数
            int low = 0,high = i -1;//折半查找区间
            while(low <= high){
                int mid = (low + high) / 2;
                if(cur < arr[mid]){
                    high = mid -1;
                }else{
                    low = mid + 1;
                }
            }
            //找到插入位置后 记录后移
            for (int j = i - 1; j >= high + 1 ; --j) {
                arr[j+1] = arr[j];
            }
            //插入
            arr[high + 1] = cur;
        }
    }

时间复杂度：

最好情况 O(n*logn) 最坏情况 O(n^2) 平均情况 O(n^2)

空间复杂度：

只需要一个辅助空间cur 保存插入的数值 O(1)

优缺点

优点：是稳定排序比直接插入排序更优
缺点：只能用于顺序表时间复杂度还是n^2量级

3.希尔排序

算法思想·：

希尔排序是基于插入排序的一种排序算法，思想是对长度为n的数组s，每趟排序基于间隔step分成几组，对每组数据使用插入排序方法进行排序，然后减小step的值，这样刚开始时候虽然分组比较多，但每组数据很少，step减小后每组数据多但基本有序，而插入排序对已经基本有序的数组排序效率较高.

代码实现：

//一次步长为step的希尔排序
    public static void shellSortOnce(int[] arr,int step){
        for (int i = step; i < arr.length; i+=step) {
            int cur = arr[i];//记录当前要插入的数
            int index = i-step;//记录需要插入到的位置 初值为分组后有序表表尾index

            //将满足插入条件的数插入到正确的位置
            while(index >= 0 && cur < arr[index] ){
                arr[index + step] = arr[index];
                index-=step;
            }
            //排除cur已经有序的情况
            if(index + step != i){
                //插入到有序表中
                arr[index + step] = cur;
            }
        }
    }

    //希尔排序
    public static void shellSort(int[] arr){
        for (int i = arr.length/2; i > 0; i/=2) {
            //根据一次递减的步长执行每次排序
            shellSortOnce(arr,i);
        }
    }

时间复杂度：

最好情况：O(n) 最坏情况O(n^2) 平均情况 O(n^1.3)

空间复杂度：

只需要一个辅助空间cur 保存插入的数值 O(1)

优缺点

优点: 在一般情况下时间复杂度由于其他的插入排序算法发现了插入算法在基本有序情况下效率高的特点并进行优化所以效率还不错适合中小规模排序
缺点：不稳定排序只能用于顺序表不适合情况简单的排序不适合大规模排序

4.冒泡排序

算法思想·：

对元素进行n -1趟排序每趟从要排序序列的第一个元素开始，一次比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。当一趟排序结束时没有出现交换情况是排序完成或者n-1趟结束后完成。

代码实现：

//冒泡排序
    public static void bubbleSort(int[] arr){
        boolean flag = false;//flag 标记是否发生交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    flag = true;//发生交换
                }
            }
            if (!flag)
                break;
            else
                flag = false;//重置flag,进行下次判断
        }
    }
    }

时间复杂度：

最好情况：O(n) 最坏情况O(n^2) 平均情况 O(n^2)

空间复杂度：

只需要一个辅助空间t 用于交换数据 O(1)

优缺点

优点: 便于理解实现简单稳定排序
缺点：时间复杂度高用于大规模数据的排序时十分吃力

5.快排

算法思想·：

快排是对冒泡的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现：

//对arr进行一趟快排(划分) 并返回排完后的枢轴位置
    private static int quickSortOnce(int[] arr,int low,int high){
        //用首元素作为枢轴数值
        int pivotKey = arr[low];
        while(low<high){
            //寻找最右侧小于枢轴的值 然后移动到最左侧
            while(high > low && arr[high] >= pivotKey)  --high;
            arr[low] = arr[high];
            //寻找最左侧大于枢轴的值 然后移动到最右侧
            while(low < high &&arr[low] <= pivotKey)  ++low;
            arr[high] = arr[low];
        }
        //将枢轴放入
        arr[low] = pivotKey;
        return low;
    }

    private static void quickSort(int[] arr,int low,int high){
        if(low < high){//递归结束条件
            int pivot = quickSortOnce(arr, low, high);
            quickSort(arr,low,pivot-1);
            quickSort(arr,pivot+1,high);
        }
    }
    //快排
    public static void qSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }

时间复杂度：

最好情况：O(nlogn) 最坏情况O(n^2) 平均情况 O(n^2)

空间复杂度：

需要栈存放临时数据等于递归树的深度最坏O(n) 最好O(logn)

优缺点

优点: 非常快
缺点：时间复杂度上已经十分优秀但是空间上并不是最优解

6.简单选择排序

算法思想·：

第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换
第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换
第三次从 arr[2]~arr[n-1]中选取最小值，与 arr[2] 交换…
第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换…
第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换。

代码实现：

 //简单选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];//假设当前值最小
            int minIndex = i;//记录最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

时间复杂度：

最好情况：O(n^2) 最坏情况O(n^2) 平均情况 O(n^2)

空间复杂度：

只需要一个空间用于交换 O(1)

优缺点

优点: 移动次数少
缺点：比较的次数多时间复杂度高

7.堆排序

算法思想·：

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。既然堆顶元素永远都是整棵树中的最大值，那么我们将数据构建成堆后，只需要从堆顶取元素不就好了吗？第一次取的元素，就是最大值。取完后把堆重新构建一下，然后再取堆顶的元素，取的就是第二大的值。反复的取，取出来的数据也就是有序的数据。堆排序可以说是一种利用堆的概念来排序的选择排序。

代码实现：

 //堆排序
    public static void heapSort(int[] arr) {
        //将无序序列构建成一个堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        //将堆顶元素和末尾元素交换,将最大元素放置数组末端
        //重新调整至堆结构,然后继续将堆顶元素和当前末尾元素交换,以此往复
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 将二叉树调整为堆
     *
     * @param arr    待调整的数组
     * @param i      表示非叶子结点在数组中索引
     * @param length 表示对多少个元素继续调整,length逐渐减少
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //k=2i+1是i的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1])//左子节点的值<右子节点的值
                k++;//指向右节点
            if (arr[k] > temp) {//如果子结点的值>父节点的值
                arr[i] = arr[k];//将较大的值赋给当前节点
                i = k;//i指向k,继续循环比较
            } else
                break;
        }
        //for循环后,已经将以i为父结点的树的最大值,放在了顶部
        arr[i] = temp;//将temp值放到调整后的位置
    }

时间复杂度：

最好情况：O(nlogn) 最坏情况O(nlogn) 平均情况 O(nlogn)

空间复杂度：

只需要一个空间用于交换 O(1)

优缺点

优点: 无论在何种情况，都非常快
缺点：针对每次不同数据都要重新建堆

8.归并排序

算法思想·：

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

这样归并排序的原理就很容易理解了：首先，对于一个无序的长序列，可以把它分解为若干个有序的子序列，然后依次进行归并。如果我们说每一个数字都是单独有序的序列，那么只要把原始长序列依次分解，直到每个子序列都只有一个元素的时候，再依次把所有的序列进行归并，直到序列数为1，这样就完成了排序。

代码实现：

     //归并排序
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            mergeSort(arr, left, mid, temp);//向左递归分解
            mergeSort(arr, mid + 1, right, temp);//向右递归分解
            merge(arr, left, mid, right, temp);//合并
        }
    }

    //合并方法
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//i为指向左边序列第一个元素的索引
        int j = mid + 1;//j为指向右边序列第一个元素的索引
        int t = 0;//指向临时temp数组的当前索引

        //先把左右两边有序数据按规则存入temp数组中,直到有一边的数据全部填充temp中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        //将有剩余数据的一边全部存入temp中
        while (i <= mid) {//左边序列有剩余元素
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right) {//右边序列有剩余元素
            temp[t] = arr[j];
            t++;
            j++;
        }

        /**
         * 将temp中的元素拷贝到arr中
         *  注意:不是每次都拷贝全部元素
         *  第一次:tempLeft=0,right=1
         *  第二次:tempLeft=2,right=3
         *  第三次:tempLeft=0,right=3
         */
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }

时间复杂度：

最好情况：O(nlogn) 最坏情况O(nlogn) 平均情况 O(nlogn)

空间复杂度：

需要和数据登场的辅助空间 O(n)

优缺点

优点: 时间复杂度低
缺点：空间复杂度高

9.基数排序

算法思想·：

将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

代码实现：

     //归并排序
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            mergeSort(arr, left, mid, temp);//向左递归分解
            mergeSort(arr, mid + 1, right, temp);//向右递归分解
            merge(arr, left, mid, right, temp);//合并
        }
    }

    //合并方法
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;//i为指向左边序列第一个元素的索引
        int j = mid + 1;//j为指向右边序列第一个元素的索引
        int t = 0;//指向临时temp数组的当前索引

        //先把左右两边有序数据按规则存入temp数组中,直到有一边的数据全部填充temp中
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }

        //将有剩余数据的一边全部存入temp中
        while (i <= mid) {//左边序列有剩余元素
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right) {//右边序列有剩余元素
            temp[t] = arr[j];
            t++;
            j++;
        }

        /**
         * 将temp中的元素拷贝到arr中
         *  注意:不是每次都拷贝全部元素
         *  第一次:tempLeft=0,right=1
         *  第二次:tempLeft=2,right=3
         *  第三次:tempLeft=0,right=3
         */
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }

时间复杂度：

最好情况：O(nk) 最坏情况O(nk) 平均情况 O(n*k)

空间复杂度：

空间复杂度我们也可以看出来,主要就是取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)

优缺点

优点: 时间复杂度低稳定
缺点：利用空间换时间空间复杂度高

测试代码如下：

import java.util.Arrays;

public class Test {
    public static void testDirectInsert(int[] nums){
        Sort.DirectInsert(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void testBinInsert(int[] nums){
        Sort.BinInsert(nums);
        System.out.println(Arrays.toString(nums));

    }
    public static void testShellSort(int[] nums){
        Sort.shellSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void testBubbleSort(int[] nums){
        Sort.bubbleSort(nums);
        System.out.println(Arrays.toString(nums));

    }


    public static void testQSort(int[] nums){
        Sort.qSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void testSelectSort(int[] nums){
        Sort.selectSort(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void testHeapSort(int[] nums){
        Sort.heapSort(nums);
        System.out.println(Arrays.toString(nums));

    }
    public static void testMergeSort(int[] nums){
        int[] temp = new int[nums.length];//归并排序需要额外的空间
        Sort.mergeSort(nums,0,nums.length,temp);
        System.out.println(Arrays.toString(nums));

    }
    public static void testRadixSort(int[] nums){
        Sort.radixSort(nums);
        System.out.println(Arrays.toString(nums));

    }
    public static void main(String[] args) {
        int[] nums = {3,1,6,9,4,22,11,8};
        System.out.println(Arrays.toString(nums));
        //testDirectInsert(nums);

        //testBinInsert(nums);
        testSelectSort(nums);
        //testShellSort(nums);
        //testBubbleSort(nums);
        //testQSort(nums);
        //testHeapSort(nums);
        //testRadixSort(nums);
    }
}