五大排序

1.选择排序
首先找到序列中最小的元素并将它与序列中第一个元素交换，最小元素归位。然后从第二个元素开始扫描，找到剩下n-1个元素中最小的元素与第二个元素交换，将第二小元素归位。以此类推，扫描n-1遍后排序完成。

    private static void selectionSort(int[] a){
        for(int i=0;i<a.length-1;i++){
            int min=i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[min]){
                    min = j;
                }
            }
            swap(a, i, min);
        }
    }

2.冒泡排序
依次比较相邻的两个数，将小数放前，大数放后。即：

• 首先比较第1个数和第2个数，将小数放前，大数放后，然后比较第2个数和第3个数，将小数放前，大数放后，直至比较最后两个数，将小数放前，大数放后，至此第一趟结束，将最大的数放在了最后。
• 仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束。
• 重复以上过程，直至完成排序。

第i遍需要扫描的元素下标范围为[0, n-1-i)

 private static void bubbleSort(int[] a){
         for(int i=0;i<a.length-1;i++){
             bool flag=false;
             for(int j=0;j<a.length-1-i;j++){
                 if(a[j]>a[j+1])
                  {
                     swap(a, j, j+1);
                     flag=true;
                  }
             }
             if(flag == false) return; //本趟遍历没有发生交换,说明已经有序
         }
     }

3.插入排序

• 从第一个元素开始，该元素被认为已经排序。
• 取出下一个元素（新元素），在已排序的序列中从后向前扫描，如果新元素小于已排序的元素，则将已排序元素后移一位，直到找到已排序元素小于或等于新元素的位置
• 将新元素放到该位置。

    private static void insertSort(int[] a){
        for(int i=1;i<a.length;i++){
            int cur = a[i];
            int j = i;
            while(j>0 && cur<a[j-1]){
                a[j] = a[j-1];
                j--;
            }
            a[j]=cur;
        }
    }

4.归并排序
归并排序算法在接近数组中间的位置划分数组，然后使用递归运算对两个一半元素构成的数组进行排序，最后将两个有序子数组进行合并，形成一个新的已排好序的数组。

    private static void mergeSort(int[] a, int left, int right){
        int[] b = new int[a.length];
        mSort(a, b, left, right);
    }
    /*
     * 当left==right时，只有一个元素，之后开始合并，在合并过程中排序；否则递归下去
     */
    private static void mSort(int[] a, int[] b, int left, int right){
        if(left < right){
            int i = (left + right)/2;
            mSort(a, b, left, i);
            mSort(a, b, i+1, right);
            merge(a, b, left, i, right);//合并到数组b
            copy(a, b, left, right);//复制回数组a
        }
    }
    
    //合并a[l:m]和a[m+1:r]到b[l:r]
    private static void merge(int[] a, int[] b, int l, int m, int r){
        int i=l, j=m+1, k=l;
        while(i<=m && j<=r){
            if(a[i]<=a[j]){
                b[k++]=a[i++];
            }else{
                b[k++]=a[j++];
            }
        }
        if(i>m){
            while(j<=r){
                b[k++]=a[j++];
            }
        }else{
            while(i<=m){
                b[k++]=a[i++];
            }
        }

    }
    
    //拷贝数组b中元素到数组a
    private static void copy(int[] a, int[] b, int left, int right){
        for(int i = left; i <= right; i++)
            a[i] = b[i];
    }

5.快速排序
快速排序与合并排序有着很多相似性。将要排序的数组分成两个子数组，通过两次递归调用分别对两个数组进行排序，再将已经排好序的两个数组合并成一个独立的有序数组。但是，将数组一分为二的做法比合并排序中使用的方法复杂。它需要将所有小于或者等于基准元素的元素放置到基准元素前面的位置，将大于基准的元素放置到基准后面的位置。快速排序按照元素值大小拆分，得到两个分区（Partition）,拆分处称为分裂点（Split position）.

    private static void quickSort(int[] a, int left, int right){
        if(left < right){
            int q = partition(a, left, right);  //q为分裂点，partition为分区函数
            quickSort(a, left, q-1);
            quickSort(a, q+1, right);
        }
    }
    private static int partition(int[] a, int left, int right){
        int p=a[left];
        int i=left+1, j=right;
        while(true){
            while(i<=right && a[i]<p)  //必须把i放在前面,因为i可能超出index
                i=i+1;
            while(j>=left && a[j]>p)
                j=j-1;
            if(i>=j) break;  
            swap(a, i, j);
        }
        swap(a, left, j);
        return j; //返回分裂点下标
    }

    private static void swap(int[] list, int k, int i){
        int temp=list[k];
        list[k]=list[i];
        list[i]=temp;
    }

快速排序扩展：找出n个元素中第k小的元素

//在a[l..r]中寻找第k小的元素
int randomizedSelect(int l,int r,int k)
{
    if(l==r) return a[l];
    int i=randomizedPartition(l,r);
    int j=i-l+1; //计算前面的元素个数
    if(k<=j) return randomizedSelect(l,i,k);
    else return randomizedSelect(i+1,r,k-j);
}