常见八大排序算法

文章目录
一、直接插入排序
二、希尔排序
三、选择排序
四、堆排序
五、冒泡排序
六、快速排序
1.递归实现
2.非递归实现
七、归并排序
1.递归实现
2.非递归实现
八、计数排序

一、直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

 public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > temp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = temp;
                    break;
                }
            }
            array[j+1] = temp;
        }
    }

直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度： O(N^2)
空间复杂度： O(1) ，它是一种稳定的排序算法
稳定性：稳定

二、希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达组内元素个数为 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 temp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > temp){
                    array[j + gap] = array[j];
                }else {
                    //array[j+gap] = temp;
                    break;
                }
            }
            array[j+gap] = temp;
        }
    }

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为 gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。一般情况下记O(N^1.3)。
稳定性：不稳定
三、选择排序
选择排序的基本思想就是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

 public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = i;
            int j = i+1;
            for (; j < array.length; j++) {
                if (array[j] < array[min]){
                    min = j;
                }
            }
            //交换
            if (min != i) swap(array,min,i);
        }
    }

直接选择排序的特性总结：

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度： O(N^2)
空间复杂度： O(1)
稳定性：不稳定
四、堆排序
堆排序 (Heapsort) 是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

 public static void heapSort(int[] array){
        createBigHeap(array);
        int len = array.length-1;
        while (len != 0){
            //交换
            swap(array,0,len);
            shiftDown(array,0,len);
            len--;
        }
    }
 
    private static void createBigHeap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
 
    private static void shiftDown(int[] array, int parent, int len) {
        int child = 2*parent+1;
        while (child < len){
            if (child + 1 < len && array[child] < array[child+1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

堆排序的特性总结：

堆排序使用堆来选数，效率就高了很多。
时间复杂度： O(N*logN)
空间复杂度： O(1)
稳定性：不稳定
五、冒泡排序

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

冒泡排序的特性总结：

冒泡排序是一种非常容易理解的排序
时间复杂度： O(N^2)
空间复杂度： O(1)
稳定性：稳定
六、快速排序
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
1.递归实现

Hoare法：

 public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
 
    private static void quick(int[] array, int start, int end) {
        if (start >= end){
            return;
        }
        //优化：后面几层采用插入排序
        if (end-start+1 <= 10){
            insertSort(array,start,end);
        }
        //优化：三数取中法
        int index = findMidIndex(array,start,end);
        swap(array,start,index);
        int pivot = partition1(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static void insertSort(int[] array,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > temp){
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = temp;
                    break;
                }
            }
            array[j+1] = temp;
        }
    }
 
    private static int findMidIndex(int[] array, int start, int end) {
        int mid = (start + end)>>1;
        if (array[start] < array[end]){
            if(array[mid] < array[start]){
                return start;
            }else if(array[mid] > array[end]){
                return end;
            }else {
                return mid;
            }
        }else {
            if(array[mid]<array[end]){
                return end;
            }else if(array[mid] > array[start]){
                return start;
            }else {
                return mid;
            }
        }
    }
 
    //Hoare法
    private static int partition(int[] array, int left, int right) {
        int i = left;
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            while (left < right && array[left] <= pivot){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }

挖坑法：

//挖坑法
    private static int partition1(int[] array, int left, int right) {
        int i = left;
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }

2.非递归实现

//非递归实现快排
    public static void quickSort1(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition1(array,left,right);
        if (pivot > left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if (right > pivot+1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while ( !stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition1(array,left,right);
            if (pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (right > pivot+1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

快速排序总结：

快速排序整体的综合性能和使用场景都是比较好的。
时间复杂度： O(N*logN)
优化后的空间复杂度： O(logN)
稳定性：不稳定
七、归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
1.递归实现

//归并排序
    public static void mergeSort(int[] array){
        mergeSortChild(array,0,array.length-1);
    }
 
    private static void mergeSortChild(int[] array, int left, int right) {
        if (left == right){
            return;
        }
        int mid = (left+right)>>1;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid+1,right);
        merge(array,left,mid,right);
    }
 
    private static void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] arr = new int[right-left+1];
        int k = 0;
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] < array[s2]){
                arr[k++] = array[s1++];
            }else {
                arr[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            arr[k++] = array[s1++];
        }
        while (s2 <= e2){
            arr[k++] = array[s2++];
        }
        for (int i = 0; i < k; i++) {
            array[left+i] = arr[i];
        }
    }

2.非递归实现

//非递归实现归并排序
public static void mergeSort1(int[] array){
    int gap = 1;
    while (gap < array.length){
        for (int i = 0; i < array.length; i+=gap*2) {
            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;
    }
}
归并排序总结 ：
1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(N)
4. 稳定性：稳定
**海量数据的排序问题：**
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G ，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

## 八、计数排序

计数排序思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

 //计数排序
    public static void countSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
            if(array[i] < minVal) {
                minVal = array[i];
            }
        }
        int len = maxVal - minVal + 1 ;
        int[] countArr = new int[len];
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            countArr[val-minVal] ++;
        }
 
        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i+minVal;
                index++;
                countArr[i]--;
            }
        }
    }