【算法】七大排序算法

妖狐艹你老母 2023-09-26 23:01 97阅读 0赞

## 一、冒泡排序 ##

1.  **实现思路**

> 冒泡排序是一种简单的排序算法，它通过重复地交换相邻的元素来将一个序列（数组）按照升序或降序排列。具体实现如下：
> 
> 1.  从序列的第一个元素开始，对相邻的两个元素进行比较，如果顺序不正确则交换它们的位置。
> 2.  继续对每一对相邻元素进行比较和交换操作，直到把最后一个元素和它之前的元素完成比较。
> 3.  重复以上步骤，每次都将未排序序列中的最后一个元素排除掉，直到整个序列有序。

1.  **代码实现**

/**
         * 冒泡排序的优化算法
         * 时间复杂度：O(N^2)
         * 空间复杂度：O(1)
         * *稳定性排序算法
         */
        public static void bubbleSortPlus(int[] arr){
        
            int temp;
            for (int i = 0; i < arr.length ; i++) {
        
                //布尔值标记当前数组是否已经达到有序状态
                boolean flag =true;
                for (int j = 0; j < arr.length-1-i ; j++) {
        
                    if (arr[j]>arr[j+1]){
        
                        temp=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=temp;
                        //本次发生了交换
                        flag =false;
                    }
                }
                //根据标记值判断数组是否有序，如果有序则退出，无序继续循环
                if (flag){
        
                    break;
                }
            }
        }

## 二、插入排序 ##

1.  **实现思路**

> 插入排序是一种简单的排序算法，它将一个序列（数组）分为已排序和未排序两个部分，初始状态下已排序部分只包含序列的第一个元素，然后逐一将未排序部分的元素插入到已排序部分的适当位置，直到整个序列有序为止。具体实现如下：
> 
> 1.  从序列的第二个元素开始，将它插入到已排序部分的适当位置，使得插入后仍然保持有序；
> 2.  继续对序列中的下一个元素进行插入操作，直到把所有元素都插入到已排序部分。

1.  **代码实现**

/**
         * 直接插入排序
         * 时间复杂度:O(n^2)
         * 稳定排序算法
         * 在近乎有序的数组排序时，性能甚至优于NlogN排序算法
         * 插入排序经常用作高阶排序算法的优化手段
         */
    
        //每次从无序区间选择一个数插入到有序区间合适的位置，直到整个数组有序
        public static void insertSort(int[] arr){
        
            //已排序区间[0,i)
            //无序区间[i,n]
            for (int i = 1; i < arr.length; i++) {
        
                //待排序区间的第一个元素是arr[i]
                //从待排序区间的第一个元素向前看，在已排序区间找到合适的位置
                for (int j = i; j >0 ; j--) {
        
                    if (arr[j]>=arr[j-1]){
        
                        //相等不交换，保证稳定性
                    //arr[j-1]为有序区间的最后一个元素，表明arr[j]大于整个区间，直接下次循环
                    break;
                    }else {
        
                        swap(arr,j,j-1);
                    }
                }
            }
        }
        private static void swap(int[] arr, int i, int j) {
        
            int temp= arr[i];
            arr[i] =arr[j];
            arr[j]=temp;
        }

## 三、折半插入排序 ##

1.  **实现思路**

> 折半插入排序（Binary Insertion Sort）是插入排序的一种优化算法。它利用了二分查找的思想，在已排序部分中找到插入位置，从而减少了比较的次数，提高了排序效率。  
> 具体实现步骤如下：
> 
> 1.  将第一个元素看作已排序部分，将第二个元素到最后一个元素看作未排序部分。
> 2.  遍历未排序部分，对于每个元素，使用二分查找在已排序部分中找到插入位置，并将其插入到已排序部分的合适位置。
> 3.  重复执行步骤 2，直到未排序部分中所有元素都被插入到已排序部分。

1.  **代码实现**

/**
         * 时间复杂度:O(n^2)
         * 稳定排序算法
         **/
      public static void binaryInsertionSort(int[] arr) {
        
            int n = arr.length;
            for (int i = 1; i < n; i++) {
        
                // 使用二分查找找到插入位置
                int left = 0, right = i - 1;
                while (left <= right) {
        
                    int mid = (left + right) / 2;
                    if (arr[mid] < arr[i]) {
        
                        left = mid + 1;
                    } else {
        
                        right = mid - 1;
                    }
                }
    
                // 将元素插入到已排序部分的合适位置
                int temp = arr[i];
                for (int j = i - 1; j >= left; j--) {
        
                    arr[j + 1] = arr[j];
                }
                arr[left] = temp;
            }
        }

## 四、选择排序 ##

1.  **实现思路**

> 选择排序是一种简单直观的排序算法，其基本思路是：每次从未排序的序列中选取最小的元素，将其放到已排序序列的末尾，直到所有元素都排好序。具体实现步骤如下：
> 
> 1.  遍历整个数组，找到最小的元素。
> 2.  将最小元素和未排序部分的第一个元素交换位置，此时第一个元素为已排序部分的最后一个元素。
> 3.  对未排序部分重复步骤 1 和 2，直到所有元素都排好序。

1.  **代码实现**

/**
         * 选择排序
         * 时间复杂度 ：O(n^2)
         * 不稳定
         */
        public static void selectionSort(int[] arr){
        
            //优化
            if (arr==null || arr.length<2){
        
                //只有一个元素或者没有元素 直接返回
                return;
            }
            for (int i=0;i<arr.length-1;i++){
        
                //min对应无序最小值的索引
                int min=i;
                for (int j=i+1;j<arr.length;j++){
        
                    //更新最小元素的索引
                    min =arr[j]<arr[min] ?j:min;
                }
                //经过内层循环，min对应无序区间的最小值，将最小值交换到有序区间
                swap(arr,i,min);
            }
        }
           //交换元素
        private static void swap(int[] arr, int i, int j) {
        
            int temp= arr[i];
            arr[i] =arr[j];
            arr[j]=temp;
        }

## 五、双向选择排序 ##

1.  **实现思路**

> 双向选择排序（Bidirectional Selection Sort）也叫鸡尾酒排序（Cocktail Sort），是选择排序的变种。它通过在每轮排序中同时从左边和右边找到未排序部分中的最小值和最大值，然后将它们放到已排序部分的左端和右端，从而减少排序的轮数。具体实现步骤如下：
> 
> 1.  初始化左边界 left 和右边界 right 分别为 0 和 n-1。
> 2.  在每轮排序中，先从左边开始遍历未排序部分，找到最小值，并将其放到已排序部分的左端。
> 3.  接着从右边开始遍历未排序部分，找到最大值，并将其放到已排序部分的右端。
> 4.  缩小左边界 left，扩大右边界 right。
> 5.  重复执行步骤 2 到步骤 4，直到左边界和右边界相遇，即整个数组有序。

1.  **代码实现**

/**
    	 * 双向选择排序
     	* 时间复杂度 ：O(n^2)
     	* 不稳定
    	 * 性能优于单向选择排序
    	 * 每次从数组无序区间取出最大和最小的元素分别放到有序区间的末尾和开始位置
         * 重复上述步骤，直到整个数组有序
     	*/
        public static void selectSortOP(int[] arr){
        
            int low=0;
            int high=arr.length-1;
            //循环遍历数组
            //low=high,表明无序区间只剩下一个元素，整个数组已经有序
            while (low<high){
        
                //最小值对应的索引
                int min=low;
                //最大值对应的索引
                int max=low;
                for (int i = low+1; i <=high ; i++) {
        
                    //将最小值交换到对应位置
                    if (arr[i]<arr[min]){
        
                    min=i;
                    }
                    //将最大值交换到对应的位置
                    if (arr[i]>arr[max]){
        
                    max=i;
                    }
                }
                //min索引对应当前无序区间的最小值，与low交换位置
                swap(arr,low,min);
                if (max==low){
        
                    //最大值已经交换到min这个位置
                    max=min;
                }
                swap(arr,high,max);
                low=low+1;
                high=high-1;
            }
        }
    
        private static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

## 六、快速排序 ##

1.  **实现思路**

> 快速排序（Quick Sort）是一种基于比较的排序算法，它采用了分治的思想，将待排序序列划分成两个子序列，使得左边子序列中的所有元素都小于右边子序列中的所有元素，然后再分别对左右子序列进行递归排序，最终将整个序列排序完成。  
> 具体实现步骤如下：
> 
> 1.  选择一个枢轴元素，一般情况下选择第一个或最后一个元素。
> 2.  划分操作：将序列分成两个部分，使得左边部分的元素都小于枢轴元素，右边部分的元素都大于枢轴元素。这个过程可以使用双指针法或单指针法实现，具体实现可以参考下面的示例代码。
> 3.  对左右两个部分分别进行递归排序，直到整个序列有序。

1.  **代码实现**

/**
         	* 快速排序
         	* 时间复杂度：O(NlogN)~O(N^2) 平均值为：NlogN
         	* 空间复杂度：O(logN)
        	 * 不稳定的排序算法
        	 * @param arr
        	 */
        public static void quickSort(int[] arr, int left, int right) {
        
            if (left < right) {
        
                // 划分操作
                int pivot = partition(arr, left, right);
                // 递归排序左右子序列
                quickSort(arr, left, pivot - 1);
                quickSort(arr, pivot + 1, right);
            }
        }
    	//分区函数，找到基准值
        public static int partition(int[] arr, int left, int right) {
        
            // 选择第一个元素作为枢轴元素
            int pivot = arr[left];
            int i = left, j = right;
            while (i < j) {
        
                while (i < j && arr[j] >= pivot) {
        
                    j--;
                }
                if (i < j) {
        
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < pivot) {
        
                    i++;
                }
                if (i < j) {
        
                    arr[j--] = arr[i];
                }
            }
            arr[i] = pivot;
            return i;
        }

## 七、堆排序 ##

1.  实现思路

> 堆排序是一种基于堆数据结构的排序算法，其思想是利用堆这种数据结构的特点，使得每次取出堆顶元素都是当前堆中最大或最小的元素，然后将其放到序列的末尾，从而完成排序。  
> 具体来说，堆排序的过程分为以下几个阶段：
> 
> 1.  根据拿到的数组构建大顶堆/小顶堆；
> 2.  从堆顶取走元素，放到其应该存在的位置中去。从堆底拿到堆中最后一个元素，放到堆顶，此时这个堆很可能不再合法也就是说不再是一个堆；
> 3.  维护这个堆，通过自己写的方法调整堆中节点结构，让它重新变成一个堆；
> 4.  重复2,3过程，直到堆被取空，此时数组也被完全排列好；

1.  代码实现

/**
         * 堆排序
         * 时间复杂度： nlogN
         * 稳定排序算法
         */
        public static void heapSort(int[] arr){
        
            //1、先将数组调整为最大堆
            //从最后一个非叶子节点来时进行元素下沉
            for (int i=(arr.length-1-1)/2; i>=0;i--){
        
                //下沉终止位置就是arr.length
                siftDown(arr,i,arr.length);
            }
            //此时，数组已经被调整为最大堆，遍历数组
            for (int i = arr.length-1; i >0 ; i--) {
        
                //arr[0]:堆顶元素，就是最大值
                swap(arr,0,i);
                siftDown(arr,0,i);
            }
        }
    
        /**
         * 元素下沉操作
         * @param arr
         * @param i     当前下沉的索引
         * @param length 数组长度
         */
        private static void siftDown(int[] arr, int i, int length) {
        
            //只有当前节点存在左右孩子时元素才可以下沉
            while (2*i+1<length){
        
                int j =(i<<1)+1;
                if (j+1<length && arr[j+1]> arr[j]){
        
                    //此时，右子树为最大值
                    j=j+1;
                }
                //当前元素已经大于左右子树的最大值
                if (arr[i] > arr[j]){
        
                    //下沉结束
                    break;
                }else {
        
                    //交换俩元素的位置
                    swap(arr,i,j);
                    //继续向后遍历，下沉元素
                    i=j;
                }
            }
        }