八大排序算法（内含思维导图和画图分析）-灵析社区

什么是排序

排序：就是让一串数据，按照其中的某个或某些关键字大小，递增或递减排列起来的操作。

内部排序：数据元素全部放在内存中的排序

外部排序：数据元素太多不能同时放在内存中的时候，根据排序过程中的要求不能在内外存之间移动的排序。

稳定性：在经过排序后，这些数据的相对次序还保持不变，则这种排序算法就是稳定的

常见的排序算法

插入排序

基本思想

就是将待排序的记录按关键值的大小一个一个插入已经先排好有序的序列中，直到所有的记录插入完为止，这样就可以得到一个新的有序序列。

我们打牌时的摸牌过程就是这个思想：

直接插入排序

它的操作就是从第二个元素开始向前比较，前面的元素大就交换，把前面的元素比较完，这就是第一轮。然后第二轮就是开始从第三个元素向前比较，以此到最后一个元素。这里比较过后的元素就是有序的了，所以要是在比较的过程中发现前面的元素比比较元素小就不必继续比较下去了，直接进入下一轮。

特点：

元素越有序，直接插入排序的时间效率越来越高

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

具体代码

//直接插入排序
    /*
    *时间复杂度 O(n^2)
    *空间复杂度 O(1)
    *稳定性： 稳定
     */
public static void initorderSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = 0;
            for(j = i - 1; j >= 0; j--) {
                if(array[j] > array[j+1]) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
                array[j+1] = tmp;
            }
        }
    }

画图分析

希尔排序

它的基本思想就是选定一个整数 gap ，把需要排序的数据分成若干份，将间隔这个数的数据放在一组，并对每个组进行直接插入排序，这是一轮。然后再重复以上步骤，只不过 gap 每次 /2 ，知道 gao=1 时，全部的数据再排序就排好序了。

特性：

希尔排序是对直接插入排序的优化

gap>1 时，属于预排序，这样可以让排序更加接近有序。gap==1 时，数据就是有序了，这时直接插入排序效率就是会很高

时间复杂度：O(N^1.25~1.6*N^1.25)

空间复杂度：O(1)

稳定性：稳定

具体代码

public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[gap];
            int j = 0;
            for (j = i - gap; j >= 0; j-=gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

画图分析

选择排序

基本思想

每一次从需要排序中的元素中挑出最小的元素放在数据的起始位置，不断重复以上操作，每操作完一轮最小元素放入的位置要往后走一个，直到数全部排序完成。

直接选择排序

在数据中 array[i] ~ array[n-1] 中选择最小的元素

将他与这组数据的第一个元素交换

在剩下的 array[i] ~ array[n-1] 中，不断重复以上操作

特性：

这个排序易理解，但效率地下，实际很少使用

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：不稳定

具体代码

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

画图分析

堆排序

堆排序是指利用堆这种数据结构设计的一种排序算法，它是通过堆来进行的选择数据。排升序是建大堆，排降序建小堆。

特性：

堆排序使用堆来排序，效率就有明显的提高

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：稳定

具体代码

public static void heapSort(int[] array) {
        createHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            siftDowm(array,0, end);
            end--;
        }
    }
    private static void siftDowm(int[]array, int parent, int len) {
        int child = 2*parent + 1;
        while(child < len) {
            if(child+1 < len && array[child+1] > array[child]) {
                child+=1;
            }
            if(array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }
        }
    }
    private static void createHeap(int[] array) {
        if(array.length == 0) {
            return;
        }
        int parent = (array.length - 1 - 1) / 2;
        for (int i = parent; i >= 0 ; i--) {
            siftDowm(array, parent, array.length);
        }
    }

画图分析

交换排序

基本思想就是根据数据中两个元素的比较结果来交换这两个数据的位置，它的特点就是将值大的元素向后移动，小的向前移动

冒泡排序

冒泡排序就是进行 n-1 趟比较排序，每一趟都比较 n-1 次，每比较完一次都减一次比较

特性：

易于理解

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

具体代码

 public static void bubbleSort(int[] array) {
        int len = array.length;
        for(int i = 0; i < len - 1; i++) {
            boolean flag = false;
            for(int j = 0; j < len - 1 - i; j++) {
                if (array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

画图分析

快速排序

它是一种二叉树结构的交换排序算法。基本思想就是去待排序中的任意一个元素作为基准值，按照这个基准值将数据分割为两个子序列，左边的都小于基准值，右边的都大于基准值，然后左右子序列再重复以上操作，知道最后元素都已经有序。

特性：

快速排序的性能和使用场景都是比较好的

时间复杂度：O(N*logN)

空间复杂度：O(logN)

稳定性：不稳定

具体代码

递归版

  public static void quickSort(int[] array, int start, int end) {
        if(start >= end) {
            return;
        }
        int key = array[start];
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && array[right] >= key) {
                right--;
            }
            while(left < right && array[left] <= key) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, start, left);
        //左子树
        quickSort(array, start, left - 1);
        //右子树
        quickSort(array, left+1, end);
    }

非递归版

public static void quickSortnor(int[] array, int start, int end) {
        Stack<Integer> stack = new Stack<>();
        int pivot = partition(array, start, end);
        if(pivot- 1 > start) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if(pivot+1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }
 
        while(!stack.isEmpty()) {
            int right = stack.pop();
            int left = stack.pop();
             pivot = partition(array, left, right);
            if(pivot - 1 > left) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if(pivot+1 < right) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
     }
    private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            } 
            array[i] = array[j];
            while (i < j && array[i] <= pivot) {
                i++;
            } 
        array[j] = array[i];
        } 
        array[i] = pivot;
        return i;
    }

画图分析

递归：

非递归：

归并排序

基本思想

归并排序是建立在归并操作上的一种有效的排序算法，它采用的是分治法，将已有序的序列合并，得到完全有序的序列。就是先让子序列有序，再使子序列何合并有序，这样叫做二路归并。

特性

归并排序的缺点在于需要O(N)的空间复杂度，归并排序的思考是解决在磁盘中的外存排序问题

时间复杂度：O(N*logN)

空间复杂度：O(N)

稳定性：稳定

具体代码

递归版

//归并排序
    /*
     *时间复杂度:O(n*logn)
     *空间复杂度 O(logn)
     *稳定性：稳定
     */
    public static void mergeSort(int[] array, int start, int end) {
        if(start >= end) {
            return ;
        }
        //分解
        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 start, int mid, int end) {
        int s1 = start;
        int s2 = mid;
        int e1 = mid+1;
        int e2 = end;
        int i = 0;
        int[] arr = new int[end - start + 1];
        while(s1 <= s2 && e1<=e2) {
            if(array[s1] < array[e1]) {
                arr[i++] = array[s1++];
            }else {
                arr[i++] = array[e1++];
            }
        }
        while(s1 <= s2) {
            arr[i++] = array[s1++];
        }
        while(e1 <= e2) {
            arr[i++] = array[e1++];
        }
        //把排好序的数组放到原来的数组中
        for (int j = 0; j < arr.length; j++) {
            array[j+start] = arr[j];
        }
    }

非递归版

public static void mergesortNor(int[] array) {
        int gap = 1;
        while(gap < array.length) {
 
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
 
                //防止越界
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
 
            gap*=2;
        }
    }

画图分析

递归：

非递归：

海量数据的排序处理

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有一个 G，需要排序的数据有 100G

因为内存中无法把所有的数据发放下，所以需要外部排序，归并排序就是最常用的外部排序

处理方式：

先将文件分成 200 份，每个 512M

分别对 512M 排序，因为内存已经可以放的下，排序

进行 2 路归并，堆 200 份文件过归并过程，最后就会有序

排序算法复杂度与稳定性

计数排序

基本思想

计数排序是对哈希直接定址法的应用

1 统计相同的元素次数

2 根据统计的结果将序列回收到原来的序列中

具体代码

 public static void countSort(int[] array) {
        //确定长度
        int max = 0;
        int min = 0;
        for (int i = 0; i < array.length; i++) {
            if(array[i] > max) {
                max = array[i];
            }
            if(array[i] < min) {
                min = array[i];
            }
        }
        int[] count = new int[max - min + 1];
        int j = 0;
        //将相同的数的次数存储到计数数组中
        for(int i = 0; i < array.length; i++) {
            count[array[i] - min]++;
        }
        //遍历计数数组 把实际的数据写到array中
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                array[j++] = i+min;
                count[i]--;
            }
        }
    }

画图分析

特性

计数排序在数据范围集中时，效率很高，但是这种情况比较少

时间复杂度：O(范围)

空间复杂度：O(范围)

稳定性：稳定