常见排序算法实现

  💕"每一天都是值得被热爱的"💕

作者：Mylvzi 

 文章主要内容：常见排序算法实现 

1.排序的概念

  所谓排序，就是按照特定顺序重新排列序列的操作

排序的稳定性：

当一个序列中存在相同的元素时  排序过后  他们出现的顺序和原来序列的顺序一致就说明此排序稳定；否则，就不稳定

内部排序：

• 内部排序是指对数据集合完全加载到内存中进行排序的过程。
• 这种排序方法适用于数据量较小，可以在计算机内存中容纳整个数据集的情况。
• 常见的内部排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
• 内部排序的优点是速度较快，因为所有数据都在内存中，不需要频繁的读取和写入操作。

外部排序：

• 外部排序是指对大规模数据集合进行排序的方法，数据量太大，无法一次性加载到内存中。
• 这种排序方法涉及将数据分割成适当大小的块，然后在内存中对这些块进行排序，最后将排序后的块写回磁盘或其他存储介质，并合并这些块以得到最终的排序结果。
• 外部排序常用于需要处理大量数据的场景，比如数据库系统中对大型表进行排序或外部存储设备上的数据排序。
• 常见的外部排序算法包括归并排序、多路归并排序等，这些算法允许对大规模数据进行高效排序，因为它们能够有效地利用磁盘I/O操作。

常见的排序算法

1.插入排序

  插入排序是一种非常简单的排序  比如在玩扑克牌时  在发牌阶段  我们每抽取一张牌  都要从后往前去比较大小  把抽取的牌插入到合适的位置

  所以，插入排序就是将待排序的元素（抽取的牌）插入到一个已经有序的序列之中

代码实现

/**
     * 插入排序  在一个已经存在的序列中  插入到合适位置
     * 时间复杂度：
     *          最好情况：O(N)
     *          最坏情况:O(N^2)
     * 空间复杂度：
     *          O(1)
     * 稳定性：是一个稳定的排序
     * 所以对于一个有序的序列来说  插入排序就是最快的
     */
 
    public static void insertSort(int[] arr) {
 
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                // >tmp  j向后挪动
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    // 要插入的元素已经是最大的了  不需要再去比较了
                    //arr[j+1] = tmp;
                    break;
                }
            }
 
            // 跳出循环有两种情况  1.tmp是最小的需要插入到第一个元素 此时j=-1  结束条件是j不>=0了   2.else语句中的break；
            arr[j+1] = tmp;
        }
    }

 2.希尔排序（缩小增量排序）

是根据插入排序的优点来进行优化的插入排序

我们知道，插入排序对于有序化高的序列来说速度是更快的，也就是说一个序列有序化越高，使用插入排序的时间复杂度就越低，速度就越快  

所以，对于一大堆的数据来说，我们可以先进行“预排”，使其有序化程度越来越高，从而实现效率更高

设置gap  利用插入排序的思想  分组进行优化  组数不断降低  直到最后为1  最后一个进行排序时  序列的有序化程度已经很高  速度很快  

希尔排序看似繁琐  实则提高了效率  虽然要进行多次插入排序  但时间优化了很多  主要原因在于以下几个方面：

1.分组会使得待排序的数据量减小  每次排序的数据量少  时间快

2.当gap = 1时，也就是要对整个序列进行排序  虽然数据量很大  但是有序化程度高  时间快

希尔排序的分析过

  代码实现

/**
     * 希尔排序  优化的插入排序
     * 先进行预排序  跳跃式进行分组  分的组数逐渐减少  直到组数为1
     * 分组优化
     * 时间复杂度：O(N^1.3)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
 
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr,gap);
        }
    }
 
    private static void shell(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0; j-= gap) {
                // >tmp  j向后挪动
                if(arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    // 要插入的元素已经是最大的了  不需要再去比较了
                    //arr[j+1] = tmp;
                    break;
                }
            }
 
            arr[j+gap] = tmp;
        }
 
    }

3.选择排序

  选择排序也是一个比较简单的排序  其核心思想在于每次都要选择一个最小的/最大的元素位于最左边

选择排序无论你的顺序如何  都要遍历整个数组去寻找最小值/最大值  所以对于初始顺序不敏感

代码实现

    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
 
            swap(arr,i,minIndex);
        }
    }
 
    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

4.堆排

堆排 就是利用堆的特性进行排序的一种方式  

思路：

1.看条件创建堆  升序--》大根堆   降序--》小根堆

2.交换首元素和末元素  向下调整

代码实现：

    /**
     * 堆排  从小到大
     * 1.创建大根堆
     * 2.交换  向下调整
     */
 
    public static void heapSort(int[] arr) {
        creatBigHeap(arr);
        int end = arr.length-1;
        while(end > 0) {
            swap(arr,0,end);
            shiftDown(arr,0,end);
            end--;
        }
    }
 
    private static void creatBigHeap(int[] arr) {
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(arr,parent,arr.length);
        }
    }
 
    private static void shiftDown(int[] arr, int parent, int end) {
        int child = 2*parent+1;
        while (child < end) {
            // 判断左右孩子谁是最大的
            if(child+1 < end && arr[child] < arr[child+1]) {
                child++;
            }
 
            if(arr[child] > arr[parent]) {
                swap(arr,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

5.快速排序

  核心思路：分而治之

概念：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序  本质上是一个递归的过程  有序时  会出现单叉树  此时时间复杂度最高  达到0(N^2)

  

代码实现

    /**
     * 快速排序
     *时间复杂度：O(N*logN);  每次分而治之需要遍历的数字都是N  最好情况是一颗完全二叉树  高度为logN  所以时间复杂度是N*logn
     *
     * 容易溢出  占用内存大
     * 三种写法：hore法  挖坑法（推荐） 前后指针法
     * 递归方法  最好的情况是一种完全二叉树
     */
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
 
    private static void quick(int[] arr,int start,int end) {
        if(start >= end) return;
 
        if(end - start + 1 > 7) {
            insertSortRange(arr,start,end);
            return;
        }
 
        midOfThree(arr,start,end);
 
 
 
        // 获得按照规则交换后的基准值的下标
        int pivot = parttion(arr,start,end);
 
        // 遍历左子树  分而治之
        quick(arr,start,pivot-1);
 
        // 遍历右子树  分而治之
        quick(arr,pivot+1,end);
 
    }
 
    public static void insertSortRange(int[] arr,int begin,int end) {
 
        for (int i = 1; i <= end; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= begin; j--) {
                // >tmp  j向后挪动
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    // 要插入的元素已经是最大的了  不需要再去比较了
                    //arr[j+1] = tmp;
                    break;
                }
            }
 
            // 跳出循环有两种情况  1.tmp是最小的需要插入到第一个元素 此时j=-1  结束条件是j不>=0了   2.else语句中的break；
            arr[j+1] = tmp;
        }
    }
 
    private static void midOfThree(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
 
        if(arr[left] > arr[right]) swap(arr,left,right);// 保证左边元素是较小值
        if(arr[mid] > arr[right]) swap(arr,mid,right);// 保证中间元素是较小值
        if(arr[mid] > arr[left]) swap(arr,mid,left);// 此时保证left下标的值是中间大小
 
 
    }
 
 
    private static int parttionHoare(int[] arr,int left,int right) {
        int i = left;
        // 每次都选取第一个元素为基准值
        int key = arr[left];
 
        // 遍历交换
        // left  从左往右  找比Key大的
        // right 从右往左  找比key小的
        while (left < right) {
            /**
             * 为什么先走右边
             * 先走right保证他们相遇时  一定是比key值小的数据
             * 如果先走left 相遇时碰到的一定是比key大的  此时再交换  则key的左边存在比key大的数据了
             */
            // 先从右边找
            while (left < right && arr[right] >= key) {  // 等号必须要取  万一两个都是6  会陷入死循环
                right--;
            }
            // 此时right下标的元素比key小
 
            while (left < right && arr[left] <= key) {
                left++;
            }
 
            swap(arr,left,right);
        }
 
        // 使基准值位于中间（即左边都比key小  右边都比key大）
        swap(arr,i,left);
        return left;
    }
 
 
    /**
     * 快排的优化
     * 1.三数取中法：解决特殊情况 --》第一个数字是最小的  或者是最大的 减少了树的高度  开辟的空间更小
     * 2.小区间内采用插入排序  减少递归的次数（但时间有可能会增加）  降低了内存的要求
     */

parttion的第二种写法：挖坑法

 // 挖坑法
    private static int parttion2(int[] arr,int left,int right) {
        // 每次都选取第一个元素为基准值
        int key = arr[left];
 
 
        // 遍历交换
        // left  从左往右  找比Key大的
        // right 从右往左  找比key小的
        while (left < right) {
            // 先从右边找
            while (left < right && arr[right] >= key) {  // 等号必须要取  万一两个都是6  会陷入死循环
                right--;
            }
            // 此时right下标的元素比key小
            arr[left] = arr[right];
 
            while (left < right && arr[left] <= key) {
                left++;
            }
            arr[right] = arr[left];
        }
 
        // 使基准值位于中间（即左边都比key小  右边都比key大）
        arr[left] = key;
        return left;
    }

parttion的第三种写法：前后指针法

    private static int parttion(int[] arr,int left,int right) {
        // 前后指针法
        int prev = left;
        int cur = left+1;
 
        while (cur <= right) {
            // 后面那个条件：cur和prev之间必须至少间隔一个元素
            // 如果没有间隔元素  交换后又把比left大的移到了左边
            if(arr[cur] < arr[left] && arr[++prev] != arr[cur]) {
                swap(arr,cur,prev);
            }
 
            cur++;
        }
 
        // 遍历完整个数组了
        swap(arr,left,prev);
        return prev;
    }

注意：

1.parttion一共有三种写法，推荐以挖坑法为先  前后指针或者Hoare法次之

2.为什么快速排序要先走right？因为这样能够保证left和right最后相遇的位置的元素是比key小的元素交换过后仍满足条件

快速排序的非递归写法

// 快排的非递归写法
    public static void quickSortNor(int[] arr) {
        Stack stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        int pivot = parttion(arr,left,right);
        
        // 如果等于  证明pivot左边只有一个数据 此时不需要再去排列了  下面的right同理
        if(pivot-1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
 
        if (pivot + 1 < right) {
            stack.push(pivot+1);
            stack.push(right);
        }
 
        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
 
            pivot = parttion(arr,left,right);
 
            if(pivot-1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
 
            if (pivot + 1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
 
    }

 6.冒泡排序法（不做讲解）

/**
     *  冒泡排序
     *  时间复杂度：O(N^2)  最好（加了优化）O(N)
     *  空间复杂度：O(1)
     *  稳定性好
     */
 
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            boolean flg = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                    flg = true;
                }
            }
 
            if(!flg) {
                return;
            }
        }
    }

7.归并排序

   归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

分解左边   分解右边   合并

代码实现

/**
     * 归并排序：
     * 时间复杂度：O(n*logN)
     * 空间复杂度：O(N);
     * 稳定
     *
     * 分解左边  分解右边  归并(合并两个有序数组)
     *
     * 稳定的排序：冒泡  插入  归并
     */
 
    public static void mergeSort(int[] arr) {
        mergeSortFunc(arr,0,arr.length-1);
    }
 
    private static void mergeSortFunc(int[] arr, int left, int right) {
        if(left >= right) return;
 
        int mid = (left+right) / 2;
        mergeSortFunc(arr,left,mid);
        mergeSortFunc(arr,mid+1,right);
        merge(arr,left,mid,right);
 
    }
 
    private static void merge(int[] arr, int left, int mid, int right) {
        // 这里边的思路相当于是 合并两个有序序列
        int[] tmpArr = new int[right-left+1];
        int k = 0;
 
        // 分别定义两个需要合并的数组的首元素的下标
        int s1 = left;
        int s2 = mid+1;
 
        // 遍历两个数组
        while(s1 <= mid && s2 <= right) {
            if(arr[s1] < arr[s2]) {
                tmpArr[k++] = arr[s1++];
            }else {
                tmpArr[k++] = arr[s2++];
            }
        }
 
        // 出循环证明有一个数组不为空
        while(s1 <= mid) {
            tmpArr[k++] = arr[s1++];
        }
 
        while (s2 <= right) {
            tmpArr[k++] = arr[s2++];
        }
 
        // 将排序好的元素返回给原数组
        for (int i = 0; i < tmpArr.length; i++) {
            arr[i+left] = tmpArr[i];
        }
    }

非递归写法

// 归并排序的非递归写法
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while(gap < arr.length) {
            for (int i = 0; i < arr.length; i+= 2*gap) {
                int left = i;
                int mid = i+gap-1;
                int right = mid+gap;
 
                if(mid >= arr.length) {
                    mid = arr.length-1;
                }
                if(right >= arr.length) {
                    right = arr.length-1;
                }
 
                merge(arr,left,mid,right);
            }
 
            gap *= 2;
        }
    }

8.计数排序

  设置一个计数数组  用于记录待排序数组中相应元素出现的次数  并按照下标排列  最后返回给原数组

   /**
     * 计数排序
     * 时间复杂度：O(N+范围）
     * 空间复杂度：O(范围)
     * 适用于数据范围集中  数据量较小的情况
     * 稳定性好
     */
 
    public static void countSort(int[] arr) {
        // 1.得到数组的最大值和最小值（数组的下标只能从0开始）
        int minVal = arr[0];
        int maxVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
            }
 
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
        }
 
        //2.遍历arr  并在计数数组中存放对应的次数
        int[] count = new int[maxVal - minVal + 1];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - minVal]++;
        }
 
        //3.重新写入到原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i] > 0) {
                arr[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

总结：

1. 稳定的排序：插入排序  冒泡排序  归并排序

2.希尔排序的时间复杂度很复杂，到现在也没有一个具体的结论

3.初始序列顺序对排序的影响 

选择排序无论你的顺序如何  都要遍历整个数组去寻找最小值/最大值  所以对于初始顺序不敏感

4.表格汇总