描述

给定一个数组，请你编写一个函数，返回该数组排序后的形式。

示例1

  1. 输入：
  2. [5,2,3,1,4]
  4. 返回值：
  5. [1,2,3,4,5]

备注：

数组的长度不大于100000，数组中每个数的绝对值不超过10^9

  1. //提供四种排序思想
  2. public class Solution {
  3.     /**
  4.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  5.      * 将给定数组排序
  6.      * @param arr int整型一维数组 待排序的数组
  7.      * @return int整型一维数组
  8.      */
  9.     public int[] MySort (int[] arr) {
  10.         // write code here
  12.         quickSort(arr);
  13.         return arr;
  14.     }
  16.       //交换两个数组元素
  17.   public  void swapArr(int[] arr,int index1,int index2) {
  18.     int i = arr[index2];
  19.     arr[index2] = arr[index1];
  20.     arr[index1] = i;
  21.   }
  23.       //选择排序
  24.   public  void selectionSort(int[] arr) {
  25.     for(int i = 0;i<arr.length;i++) {
  26.       //寻找（i,arr.length]之间的最小值
  27.       int minIndex = i;
  28.       for(int j = i+1;j<arr.length;j++) {
  29.         if(arr[j]<arr[minIndex]) {
  30.           minIndex = j;
  31.         }
  32.       }
  33.       swapArr(arr,i,minIndex);
  34.     }
  35.   }
  37.      //将arr[l..mid] 和 arr[mid+1 ... r]两部分进行归并
  38.   private static void __merge(int[] arr,int l,int mid, int r) {
  39.     int[] aux = new int[r-l+1];
  40.     //将排序的空间赋值给aux
  41.     int i;
  42.     for(i = l;i <= r;i++) {
  43.       aux[i-l] = arr[i];
  44.     }
  45.     i=l;
  46.     int j = mid+1;
  47.     //归并排序
  48.     for(int k = l;k <= r;k++) {
  49.       //1 看i j 是否越界
  50.       if(i>mid) {
  51.         arr[k] = aux[j-l];
  52.         j++;
  53.       }else if(j>r) {
  54.         arr[k] = aux[i-l];
  55.         i++;
  56.       }else {
  57.         if(aux[i-l]<aux[j-l]) {
  58.           arr[k] = aux[i-l];
  59.           i++;
  60.         }else {
  61.           arr[k] = aux[j-l];
  62.           j++;
  63.         }
  64.       }
  65.     }
  66.   }
  67.   //递归使用归并排序，对arr[l..r] 的范围进行排序
  68.   private static void __mergeSort(int[] arr,int l,int r) {
  69.     //结束条件
  70.     if(l >= r) {
  71.       return;
  72.     }
  73.     //求中点位置
  74.     int mid = (l+r)/2;
  75.     __mergeSort(arr,l,mid);
  76.     __mergeSort(arr,mid+1,r);
  77.     //进行最后排序
  78.     __merge(arr,l,mid,r);
  79.   }
  81.   //归并排序
  82.   public static void mergeSort(int[] arr) {
  83.     //对arr[l..r] 的范围进行排序
  84.     __mergeSort(arr,0,(arr.length)-1);
  85.   }
  87.       //对arr[l...r] 部分进行partiton 操作
  88.   //返回p 使得arr[l...p-1] <arr[p] arr[p+1 ...r] >arr[p]
  89.   private int __partition(int[] arr,int l, int r) {
  90.      int v = arr[l];
  91.      // j的值指向第一个大于V的值的下标
  92.      int j = l+1;
  93.         // 遍历整个数组 一直到 i<= r 时候结束
  94.      for(int i = l+1;i<=r;i++) {
  95.              if(arr[i] < v) {
  96.          swapArr(arr, i,j);
  97.          j++;
  98.        }
  99.      }
  100.      swapArr(arr, l, j-1);
  101.     return j-1;
  102.   }
  103.   //对arr[l...r] 部分进行快速排序
  104.   private void __quickSort(int[] arr,int l,int r) {
  105.     if(l>=r) {
  106.       return;
  107.     }
  108.     int p = __partition(arr,l,r);
  109.     __quickSort(arr, l, p-1);
  110.     __quickSort(arr, p+1, r);
  111.   }
  113.   //快速排序
  114.   public void quickSort(int[] arr) {
  115.     __quickSort(arr,0,arr.length-1);
  116.   }
  117.   private  void __quickSort3Ways(int[] arr,int l,int r) {
  118.     if(r-l<=15) {
  119.       insertionSort(arr);
  120.       return;
  121.     }
  122.     Random ra = new Random();
  123.     swapArr(arr, l, ra.nextInt(r-l)+l);
  124.     int v = arr[l];
  125.     //__partition3Ways(arr,r,l);
  126.     //partiton3Ways
  127.     int lt = l;
  128.     int gt = r;
  129.     int i = l+1;
  130.     while(i<gt){
  131.       if(arr[i]>v) {
  132.         swapArr(arr, i, gt);
  133.         gt--;
  134.       }else if(arr[i]<v) {
  135.         swapArr(arr, i, lt+1);
  136.         i++;
  137.         lt++;
  138.       }else {
  139.         i++;
  140.       }
  141.     }
  143.     swapArr(arr, l, lt);
  145.     __quickSort3Ways(arr,l,lt-1);
  146.     __quickSort3Ways(arr,gt,r);
  147.   }
  149.   //三路快速排序
  150.   public void quickSort3Ways(int[] arr) {
  151.     __quickSort3Ways(arr,0,arr.length-1);
  152.   }
  154.       //插入排序
  155.   public void insertionSort(int[] arr) {
  156.     for(int i = 1; i<arr.length;i++) {
  157.       //寻找元素arr[i]合适的插入位置
  158.       int j;
  159.       for(j = i;j>0;j--) {
  160.         if(arr[j] < arr[j-1]) {
  161.                     //使用交换 需要赋值三次
  162.           swapArr(arr, j, j-1);
  163.         }else {
  164.           break;
  165.         }
  166.       }
  167.     }
  168.   }
  169. }

image.png