两种O(nlogn)级别的排序，归并排序和快速排序

悠悠 2022-06-07 20:48 250阅读 0赞

最近重新学习了算法中的排序算法，相较于几个O(n^2)级别的排序算法(冒泡排序，选择排序，插入排序，希尔排序等) O(nlogn)级别的排序算法有普遍更快的速度，相对于O(n^2)级别的排序算法来说也更难理解。下面我把我最近学习这两个排序的想法说一下。

归并排序：归并排序就是将数组不断的等分，等分到一组只有一个数，然后向上合并，例如第一次合并只有自己 就直接合并，然后就会变成两两一组 这时就有大小关系了，按照我们的规则交换之，再向上合并，最后就可以得到一个排好序的数组，大概是

private static void \_\_mergeSort\_(int\[\] arr, int l, int r) \{//l代表left r代表right  
  
            if(l >= r)\{  
               return ;  
              \}  
  
      int mid = (l + r) / 2; //这里是求得中间值 例如 0~8 就是4这个位置 4~8 就是6这个位置  
            //递归  
           \_\_mergeSort\_(arr, l, mid);     
           \_\_mergeSort\_(arr, mid + 1, r);  
  
            //调用核心  
           \_\_merge(arr, l, mid, r);  
         \}

不断的等分，然后调用比较的方法。当分成一组只有一个值的时候 就return;向上返回

快速排序：快速排序的思想就是选择一个数作为基数  去遍历数组小于的放在基数左边 大于的放在基数右边，然后根据基数的位置 递归即可求解。大概是

private static void \_\_quickSort(int\[\] arr, int l, int r) \{  
  
if(l >= r)\{  
return;  
\}

//取到这次基数的位置  
int p = \_\_partition(arr, l, r);  
\_\_quickSort(arr, l, p - 1);  
\_\_quickSort(arr, p + 1, r);  
\}

这两种算法的代码如下：

package cyd; public class NLognSort { public static void main(String[] args) { testSort(10000,0,10000); } //测试性能 public static void testSort(int size, int rangeL, int rangeR){ int[] arr = randomArr(size, rangeL, rangeR); long startTime = System.currentTimeMillis(); quickSort3Ways(arr); //boolean flag = isSortArr(arr); //判断 是否排序成功 /*if(!flag){ System.err.println("没有排序成功"); return; }*/ long endTime = System.currentTimeMillis(); System.err.println(((double)(endTime - startTime))/1000.0 + "s"); printArr(arr); } //归并排序算法 public static void mergeSort(int[] arr){ __mergeSort_(arr, 0, arr.length - 1); // 借用Python的规范，表示私有方法，不希望用户调用 } //归并算法递归实现 private static void __mergeSort_(int[] arr, int l, int r) {//l代表left r代表right if(l >= r){ return ; } //优化2 在 范围极小时，数组趋近于有序，这时可以采用插入排序 可以加快效率 /*if( r - l < 15){ insertSortArray(arr, l, r); return; }*/ int mid = (l + r) / 2; //这里是求得中间值 例如 0~8 就是4这个位置 4~8 就是6这个位置 //递归 __mergeSort_(arr, l, mid); __mergeSort_(arr, mid + 1, r); //调用核心 //优化1 由于归并算法的保证，左边和右边一定是有序的,如果左边大于了右边 //这时我们才去对它排序，这样对于较为有序的数组排序就能够提前结束 if(arr[mid] > arr[mid + 1]) __merge(arr, l, mid, r); } //归并排序算法核心 private static void __merge(int[] arr, int l, int mid, int r) { int[] aux = new int[r - l + 1]; //这是临时数组，大小为传入的 大小 也就是当前要归并的数组大小 for(int i = l ; i <= r; i ++){ aux[i - l] = arr[i]; //临时表复制 } int i = l, j = mid + 1; for(int k = l; k <= r; k++){ if(i > mid){ //如果 i大于 mid 说明左边的元素已经被排好但是 有右边的没有被排好，这时就要将右边的值写入arr并且游标右移 arr[k] = aux[j - l]; j++; } else if(j > r){ //如果 j大于 mid 说明右边边的元素已经被排好但是 有左边的没有被排好，这时就要将左边的值写入arr并且游标右移 arr[k] =aux[i - l]; i++; } else if( aux[i - l] < aux[j - l]){ //如果当前组左边小于右边 就将左边的值给arr 左边游标右移 arr[k] = aux[i - l]; i++; } else{ //剩下这种情况只能是 右边大于左边了 arr[k] = aux[j - l]; j++; } } } //快速排序 public static void quickSort(int[] arr){ __quickSort(arr , 0, arr.length - 1); } //递归实现快速排序 //每次找到当前的中间值，然后等分左右，再继续从左右依次这样做 就实现了快速排序 private static void __quickSort(int[] arr, int l, int r) { if(l >= r){ return; } //优化1 数据小的时候 几乎有序，使用插入排序 /*if( r - l < 15){ insertSortArray(arr, l, r); return; }*/ int p = __partition(arr, l, r); __quickSort(arr, l, p - 1); __quickSort(arr, p + 1, r); } //快速排序核心 private static int __partition(int[] arr, int l, int r) { //这是标准位置的值,最后排序完成左边的比这小右边的比这大 //初始版本 取第一个元素 ，但是有一个弊端 如果 数组本身近乎有序，那么大于当前值的就会非常多，导致右侧元素多，就会导致快速排序退化成O(n^2)级别的排序 // int p = arr[l]; //改进 从 l 到 r 中随机取 一个数 与 起始位置交换作为起始位置，这时 就不会出现这种情况了 swap(arr, l , (int) (Math.round((Math.random()*(r - l) + l)))); int p = arr[l]; int j = l; for(int i = l + 1; i <= r; i++){ if(arr[i] < p){ swap(arr, i , j + 1); j++; } } swap(arr, j , l); return j; } // 改进 快速 排序 如果 大量重复数的情况下，就会将等于标定点的元素都放在右边 这就又导致了 快排变成了 O(n^2) 级别的排序 //改进 public static void quickSort2(int[] arr){ __quickSort2(arr, 0, arr.length - 1); } private static void __quickSort2(int[] arr, int l, int r) { if(l >= r){ return; } int p = __partition2(arr, l, r); __quickSort2(arr, l, p - 1); __quickSort2(arr, p + 1, r); } private static int __partition2(int[] arr, int l, int r) { swap(arr, l , (int) (Math.round((Math.random()*(r - l) + l)))); int p = arr[l]; //直接将arr分成两半，左边向右检索，右边向左检索 找到两边 左边大于 arr[l]的 和 右边小于 arr[l] 的 交换 // 最后 将标定 值 和 j最后位置的值 交换 int i = l + 1; int j = r; while( true ){ while(i <= r &&arr[i] < p) i++; while(j >= l + 1 && arr[j] > p) j--; if(i > j) break; swap(arr, i ,j); i++; j--; } swap(arr, j, l); return j; } //3路快排 将 数组分成 小于 标准值 等于标准值 和 大于标准值 三部分 ，然后再对 小于部分 和大于部分3路快排 等于部分就不需要再排了 public static void quickSort3Ways(int[] arr){ __quickSort3Way(arr, 0, arr.length - 1); } private static void __quickSort3Way(int[] arr, int l, int r) { if( l >= r){ return; } // // v为pivot，初始存储在arr[l]的位置 swap(arr, l , (int) (Math.round((Math.random()*(r - l) + l)))); int p = arr[l]; int lt = l; // 循环过程中保持 arr[l+1...lt] < v int gt = r + 1; // 循环过程中保持 arr[gt...r] > v int i = l + 1; // 循环过程中保持 arr[lt+1...i) == v while( i < gt){ if(arr[i] < p){ // 这里相当于 如果小于的话 直接 将 i 和 lt 都向后移一位 /*swap(arr, i ,lt + 1);*/ //这步其实没有必要 lt++; i++; }else if(arr[i] > p){ swap(arr, i ,gt - 1); gt--; }else{ i++; } } swap(arr, l, lt); __quickSort3Way(arr, l, lt - 1); __quickSort3Way(arr, gt, r); } //插入排序 从左往右 第一个数 假设已经排好，第二个数是否小于第一个数 是的话交换，第三个数是否小于 //第二个数 小于交换 并判断 第二个数(也就是之前的第三个数) 是否小于第一个数 小于交换 。。。。。 public static void insertSortArray(int[] arr) { for (int i = 1; i < arr.length; i++) { //倒着往前遍历，如果存在 小于前一个数的 交换 否则 不交换并且break ，比选择排序 快很多 不用全部循环两次 for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) { swap(arr, j, j - 1); } } } //插入排序 排序任意位置的数 public static void insertSortArray(int[] arr,int l, int r) { for (int i = r; i < arr.length; i++) { //倒着往前遍历，如果存在 小于前一个数的 交换 否则 不交换并且break ，比选择排序 快很多 不用全部循环两次 for (int j = i; j > l && arr[j] < arr[j - 1]; j--) { swap(arr, j, j - 1); } } } //输出 public static void printArr(int[] arr){ for(int i = 0; i < arr.length; i++){ if(i != arr.length - 1){ System.err.print(arr[i]+","); }else{ System.err.println(arr[i]); } } } /** * 生成随机数 * @param size * @param rangeL * @param rangeR * @return */ public static int[] randomArr(int size, int rangeL, int rangeR){ if(rangeL >= rangeR){ return null; } int arr[] = new int[size]; for(int i = 0; i < size; i++){ arr[i] = (int) (Math.round((Math.random()*(rangeR - rangeL ) + rangeL))); for(int j = 0; j <=i; j++ ){ if(i != j){ if(arr[i] == arr[j] ){ i--; break; } } } } return arr; } public static boolean isSortArr(int[] arr){ for(int i =0 ; i < arr.length - 1; i++){ if(arr[i] > arr[i + 1]){ return false; } } return true; } //交换 public static void swap(int arr[], int leftNum, int rightNum){ int temp = arr[leftNum]; arr[leftNum] = arr[rightNum]; arr[rightNum] = temp; } }