排序---归并排序、快速排序、堆排序实现和性能分析

野性酷女 2023-06-18 08:00 134阅读 0赞

### 文章目录 ###

*   *  归并排序
     *   *   *  图解
             *  实现---方法1
             *  实现---方法2
             *  算法步骤分析
             *  性能分析
     *  快速排序
     *   *   *  图解
             *  实现
             *  算法步骤分析
             *  性能分析
     *  堆排序
     *   *   *  性能分析
     *  O(n)时间复杂度找第k大元素
     *   *   *  时间复杂度分析
     *  利用归并排序思想求逆序对个数

## 归并排序 ##

思想：递归和分治

1.  将数组一分为二
2.  对左右两边的数组又可以一分为二，直至数组只有一个元素
3.  将排好序的数组合并为有序数组

#### 图解 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]

#### 实现—方法1 ####

public class MergeSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            int[] newArr = mergeSort(arr);
            System.out.println("");
            Arrays.stream(newArr).forEach(System.out::print);
        }
    
        public static int[] mergeSort(int[] arr) { 
            return mergeSortInternally(arr, 0, arr.length - 1);
        }
    
        public static int[] mergeSortInternally(int[] arr, int left, int right) { 
            if(left >= right) return new int[] { arr[left]};
    
            int mid = (left + right) / 2;
            int[] arr1 = mergeSortInternally(arr, left, mid);
            int[] arr2 = mergeSortInternally(arr, mid + 1, right);
    
            return merge(arr1, arr2);
        }
    
        /** * 合并两个有序数组为一个数组 * @param arr1 * @param arr2 * @return */
        public static int[] merge(int[] arr1, int[] arr2) { 
            int l1 = arr1.length;
            int l2 = arr2.length;
            int[] arr = new int[l1 + l2];
    
            int i = 0;
            int j = 0;
            int k = 0;
    
            while(i < l1 && j < l2) { 
                arr[k++] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
            }
    
            while(i < l1) { 
                arr[k++] = arr1[i++];
            }
    
            while(j < l2) { 
                arr[k++] = arr2[j++];
            }
    
            return arr;
        }
    }

#### 实现—方法2 ####

public class MergeSort2 { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            mergeSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void mergeSort(int[] arr) { 
            mergeSortInternally(arr, 0, arr.length - 1);
        }
    
        public static void mergeSortInternally(int[] arr, int left, int right) { 
            if(left >= right) return;
    
            int mid = (left + right) / 2;
            mergeSortInternally(arr, left, mid);
            mergeSortInternally(arr, mid + 1, right);
    
            merge(arr, left, right, mid);
        }
    
        public static void merge(int[] arr, int left, int right, int mid) { 
            int i = left;
            int j = mid + 1;
            int[] temp = new int[right - left + 1];
            int k = 0;
    
            while(i <= mid && j <= right) { 
                temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
            }
    
            while(i <= mid) { 
                temp[k++] = arr[i++];
            }
    
            while (j <= right) { 
                temp[k++] = arr[j++];
            }
    
            int index = 0;
            for (int m = left; m <= right; m++) { 
                arr[m] = temp[index++];
            }
        }
    }

#### 算法步骤分析 ####

mergeSort函数中会两次递归调用mergeSort：  
$ left = mergeSort($arr, $l, $mid); //这个步暂且称为“左边的mergeSort”调用  
$ right = mergeSort($arr, $mid+1, $r);//这个步暂且称为“右边的mergeSort”调用

以上图的例子为例简书递归调用和合并的过程：  
（1）调用mergeSort(\[8,4,5,7,1,3,6,2\])，进入第一次“左边的mergeSort”调用  
（2）调用mergeSort(\[8,4,5,7\])，进入第二次“左边的mergeSort”调用  
（3）调用mergeSort(\[8,4\])，进入第三次“左边的mergeSort”调用  
（4）调用mergeSort(\[8\])，此时满足递归退出的条件，返回\[8\]，递归退回一次  
（5）进入第一次“右边的mergeSort”调用，mergeSort(\[4\])，此时满足递归退出的条件，返回\[4\]，递归退回一次  
（6）此时，第一次执行到merge，merge(\[8\],\[4\])，然后merge返回值为\[4,8\]，此时，递归也会退回一次。这就退回到第（3）步‘进入第三次“左边的mergeSort”调用结束后’，应该进入第二次“右边的mergeSort”调用，mergeSort(\[5,7\])  
（7）和第（3）~（6）步做同样的分析，最终会得到有序数组\[7,5\]，并且做一次递归退回。调用merge(\[4,8\],\[5,7\])，返回有序数组\[4,5,7,8\]。然后递归退回到第（2）步，进入“右边的mergeSort”调用，mergeSort(\[1,3,6,2\])  
（8）接下来的分析就和第（2）~（7）步一样，最后会得到有序数组\[1,2,3,6\]  
（9）最后一次调用merge(\[4,5,7,8,\[1,2,3,6\]\])，得到\[1,2,3,4,5,6,7,8\]

#### 性能分析 ####

1.  归并排序是否稳定取决于merge函数，在合并有序数组过程中，如\[1,1,2\]，\[1,3\]，会依次将左边数组的1，1放入临时数组中，再放入右边数组的1，所以左边数组的两个相同元素先后顺序没有改变，右边数组的1也没有插入左边数组两个1的中间。因此，该算法是**稳定的**。
2.  **最好情况、最坏情况、平均时间复杂度都是O(nlogn)**。  
    归并排序的时间复杂度和待排序数据的有序性无关，因此这三个时间复杂度相同。  
    时间复杂度计算：  
    首先，对于递归问题，将a问题分解为b和c问题，再将b的解和c的解合成a的解，则a所需要的时间可以这样表示：**T(a)=T(b)+T(c )+k，k为合并b和c为a需要的时间**。  
    其次，合并两个有序数组的时间复杂度为O(n)，n为两个数组最大元素个数。  
    现在，假设给n个元素进行归并排序需要T(n)时间，每次将数组一分为二，左右两个数组进行归并排序分别需要T(n/2)。那么，**归并排序的所需要的时间计算公式为：  
    T(n)=2\*T(n/2)+n;并且，当n=1时，T(n)=C(常量)**  
    **化解公式**：  
    T(n)=2*T(n/2)+n，把T(n/2)=2*T(n/4)+(n/2)带入原式，再用同样的方式带入T(n/4)，最终得到T(n)=2^ k\* T(n/2^ k) + kn，当2^ k趋近于n的时候，即T(n/2^ k)=T(1)，n=2^ k，得到k=log(以2为底)n，将k带入T(n)=2^ k \* T(n/2^ k) + k\* n得到T(n)=C\* n+n\* log(以2为底)n，由于时间复杂度的计算对于加号可以只需要取最大值项即可，因此，时间复杂度就为O(nlogn)。
3.  **空间复杂度是O(n)**，因为merge函数需要创建临时数组存放两个有序数组排好序之后的数组。

## 快速排序 ##

思想：递归和分区

*  将当前数组分为两个区，左边的区域比分区元素小，右边的区域比分区元素大
 *  对左右两个分区做和第1步同样的操作
 *  分区：取数组最后一个元素为区分值

#### 图解 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]

#### 实现 ####

public class QuickSort { 
        public static void main(String[] args) { 
            int[] arr = new int[10];
            Random random = new Random();
            for(int i = 0; i < 10; i++) { 
                arr[i] = random.nextInt(10);
            }
            Arrays.stream(arr).forEach(System.out::print);
            quickSort(arr);
            System.out.println("");
            Arrays.stream(arr).forEach(System.out::print);
        }
    
        public static void quickSort(int[] arr) { 
            quickSortInternally(arr, 0, arr.length - 1);
        }
    
        /** * @param arr 待排序数组 * @param left 当前需要分区的子数组第一个元素的下标 * @param right 当前需要分区的子数组左后一个元素的下标 */
        public static void quickSortInterally(int[] arr, int left, int right) { 
            if(left >= right) { 
                return;
            }
    
            int p = partition(arr, left, right);
            quickSortInterally(arr, left, p - 1);
            quickSortInterally(arr, p + 1, right);
        }
    
        /** * @param arr 待分区数组 * @param left 当前需要分区的子数组第一个元素的下标 * @param right 当前需要分区的子数组左后一个元素的下标 * @return 分区的下标 */
        public static int partition(int[] arr, int left, int right) { 
            int pivot = arr[right];
            int i = left;
            int j = left;
            int temp;
    
            while(j < right) { 
                if(arr[j] < pivot) { 
                    //遇到比pivot小的元素，则将其往前移动
                    //比如15263，当i=1 j=1时，5比3大，只让j++，j=2
                    //下一轮循环，i=1 j=2,2比3小，把2和5位置互换，将小小于pivot的元素前移
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                    i++;
                }
                j++;
            }
    
            arr[right] = arr[i];
            arr[i] = pivot;
    
            return i;
        }
    }

#### 算法步骤分析 ####

$ left = quickSort($arr, $l, $p);//这个步暂且称为“左边的quickSort”调用  
$ right = quickSort($arr, $p + 1, $r);//这个步暂且称为“右边的quickSort”调用  
以\[1,4,0,3,2\]为例：  
（1）第一次调用partition(\[1,4,0,3,2\], 0, 4)，数组变为\[1,0,2,3,4\]，返回值p为2  
（2）第一次调用“左边的quickSort”，quickSort(\[1,0,2,3,4\],0, 1)  
（3）第二次调用partition(\[1,0,2,3,4\], 0, 1)，数组变为\[0,1,2,3,4\],返回值p为0  
（4）第二次调用“左边的quickSort”，quickSort(\[0,1,2,3,4\],0, -1)，递归第一次退回  
（5）回到第（2）步之后，第一次调用“右边的quickSort”，quickSort(\[0,1,2,3,4\],3,4)  
（6）第三次调用partition(\[0,1,2,3,4\],3,4)，数组变为\[0,1,2,3,4\]，返回值p为3  
（7）再次调用“左边的quickSort”，quickSort(\[0,1,2,3,4\],3,2)，递归第二次退回  
（8）再次调用“右边的quickSort”，quickSort(\[0,1,2,3,4\],4,4)，递归第三次退回  
（9）至此，得到排序后的数组\[0,1,2,3,4\]

#### 性能分析 ####

1.  **不稳定的**。该算法的稳定性取决于partition函数，如\[1,1,0\]，pivot为0，i=0，第一次while循环中arr\[0\]不小于pivot，第二次while循环中arr\[1\]不小于pivot，退出while循环时，i=0，将arr\[0\]和arr\[2\]交换位置得到\[0,1,1\]，可以看到两个1交换了顺序，因此该排序算法不稳定。
2.  **最好和平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。**  
    快排和归并排序一样，用到了递归，当pivot几乎每次都能将数据一分为二的时候，分析方法和归并排序分析方法一样。但是，快排不同于归并之处是，快排的时间复杂度受元素有序性的影响，**当元素接近有序**，如1,2,3,4,5，每次选最后一个元素为pivot，则partition函数依次需要进行n,n-1,n-2…,1次遍历操作，总共需要n(1+n)/2次遍历，因此，这个时候，时间复杂度就退化成O(n^2)。
3.  **空间复杂度为O(1)**，即原地排序算法。

## 堆排序 ##

public class HeapSort{ 
        public static void main(String []args){ 
            int []arr = { 9,8,7,6,5,4,3,2,1};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr) { 
            int len = arr.length;
    
            // 构造大顶堆，从第一个非叶子节点开始，一个一个调整
            for(int i = len / 2 - 1; i >= 0; i--) { 
                adjuestHeep(arr, i, len);
            }
    
            // 交换，把堆顶元素和数组末尾元素交换，在从堆顶元素进行调整
            for(int j = len - 1; j > 0; j--) { 
                swap(arr, 0, j);
                adjuestHeep(arr, 0, j);
            }
        }
    
        public static void adjuestHeep(int[] arr, int i, int len) { 
            int currentItem = arr[i];
            for(int k = i * 2 + 1; k < len; k = 2 * k + 1) { 
                if(k + 1 < len && arr[k + 1] > arr[k]) { 
                    k++;
                }
                if(arr[k] > currentItem) { 
                    arr[i] = arr[k];
                    i = k;
                }else{ 
                    break;
                }
            }
            arr[i] = currentItem;
        }
    
        public static void swap(int []arr,int a ,int b){ 
            int temp=arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

#### 性能分析 ####

最好、最坏、平均时间复杂度都为O(nlogn)  
空间复杂度为O(1)  
不稳定

## O(n)时间复杂度找第k大元素 ##

> 给定无序数组，找第k大元素，时间复杂度为O(n)

利用快排序分区的思想，基准元素最终的下标p，当p+1 == k时，p所在位置的元素就是第k大元素。

import java.util.Scanner;
    
    public class Main { 
        public static void main(String[] args) { 
        	int[] arr = { 1,2,3,2,5,7,4};
            int k = 2;
            int result = find(arr, 0, arr.length - 1, arr.length - k + 1);
            System.out.println(result);
        }
        
        public static int find(int[] arr, int left, int right, int k) { 
            int p = partition(arr, left, right);
            if(p + 1 < k) { 
                return find(arr, p + 1, right, k);
            }else if(p + 1 > k) { 
                return find(arr, left, p - 1, k);
            }else { 
                return arr[p];
            }
        }
        
        public static int partition(int[] arr, int left, int right) { 
            int p = arr[right];
            int i = left;
            int j = left;
            int temp;
            
            while(j < right) { 
                if(arr[j] < p) { 
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                    i++;
                }
                j++;
            }
            
            arr[right] = arr[i];
            arr[i] = p;
            
            return i;
        }
    }

#### 时间复杂度分析 ####

第一次分区查找，我们需要对大小为n的数组执行分区操作，需要遍历n个元素。第二次分区查找，我们只需要对大小为n/2的数组执行分区操作，需要遍历n/2个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为1。如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于2n-1。所以，上述解决思路的时间复杂度就为**O(n)**。

## 利用归并排序思想求逆序对个数 ##

> 给定一个数组，计算数组元素逆序对的个数，比如2,4,3,1,5,6，逆序对有：(2,1)、(4,3)、 (4,1)、 (3,1)

public class ReverseOrderCountDemo { 
        public static void main(String[] args) { 
            int[] arr = { 2,4,3,1,5,6};
            ReverseOrderCountDemo countDemo = new ReverseOrderCountDemo();
    
            System.out.println(countDemo.count(arr));
        }
    	// 存储逆序对个数
        private int num = 0;
        /** * @param arr 目标数组 * @return 数组元素逆序对个数 */
        public int count(int[] arr) { 
            num = 0;
            mergeSortCounting(arr, 0, arr.length - 1);
            return num;
        }
    
        public void mergeSortCounting(int[] arr, int left, int right) { 
            if(left >= right) return;
    
            int mid = (left + right) / 2;
            mergeSortCounting(arr, left, mid);
            mergeSortCounting(arr,mid + 1, right);
    
            merge(arr, left, mid, right);
        }
    
        public void merge(int[] arr, int left, int mid, int right) { 
            int[] temp = new int[right - left + 1];
            int i = left;
            int j = mid + 1;
            int k = 0;
            int m = 0;
    
            while(i <= mid && j <= right) { 
                if(arr[i] <= arr[j]) { 
                    temp[k++] = arr[i++];
                }else{ 
                    // 计算从i到mid有几个元素，这些元素都比下标为j的元素大
                    num = num + mid - i + 1;
                    temp[k++] = arr[j++];
                }
            }
    
            while(i <= mid) { 
                temp[k++] = arr[i++];
            }
    
            while(j <= right) { 
                temp[k++] = arr[j++];
            }
    
            // 将arr数组从left到right的位置上的元素赋值为排序后的元素
            for(int index = left; index <= right; index++) { 
                arr[index] = temp[m++];
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215214513513.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200215203826898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70