排序

1.冒泡排序

每次将最小的元素下沉到当前数组的后面，遍历时遇到大的就交换

public class BubbleSort {
    public int[] bubbleSort(int[] A, int n) {
        // write code here
        if (n <=1) {
            return A;
        }
        //冒泡
        for (int i= n-1; i> 0; i--) {
            for (int j =0 ; j <i;j++ ) {
                if (A[j] > A[i]) {
                    int temp = A[j];
                    A[j] = A[i];
                    A[i] = temp;
                }
            }
        } 
        return A;
    }
}

2.选择排序

从头到尾，依次选择最小的元素放在前面，遍历时需要记录当前未排序元素的最小元素的下标

public class SelectionSort {
    public int[] selectionSort(int[] A, int n) {
         //选择排序
        int index = 0 ;
        for (int i=0; i< n-1; i++) {
            for (int j = i+1; j<n; j++ ) {
                if (A[index]> A[j]) {
                    index = j;
                }
            }
            int temp = A[i];
            A[i] = A[index];
            A[index] = temp;
            index = i+1;
        }
        return A;
    }
}

3.插入排序

从头到尾遍历每个元素，遍历的元素依次与其前面的元素进行比较，并把比它大的元素依次向后移动

public class InsertionSort {
    public int[] insertionSort(int[] A, int n) {
        // write code here
        //插入排序
        for(int i=1,j;i<n;i++){
            int temp=A[i];
            for(j=i;j>0&&temp<A[j-1];j--){      
                  A[j]=A[j-1];
            }
            A[j]=temp;
        }
        return A;
    }
}

4.归并排序

这里需要分两步，一个是递归的（不断的去拆待排序的元素，直到子待排序的数组只有一个元素停止递归），一个是合并（将相邻两个的有序数组合并为一个更大的有序数组，需要用到一个额外的数组空间）

public class MergeSort {
    public int[] mergeSort(int[] A, int n) {
        if(A == null || n <2) {
            return A;
        }
        process(A, 0, n-1);
        return A;
    }
    private void process(int[] a, int left, int right) {
        if (left == right) {
            return ;
        }
        int mid = (left+right) /2;
        process(a, left, mid);
        process(a, mid+1, right);
        merge(a, left, mid, right);
    }
    private void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left +1];
        int l = left;
        int r = mid + 1;
        int index = 0;
        while (l <= mid && r <= right) {
            if (arr[l] <= arr[r]) {
                help[index++] = arr[l++];
            } else {
                help[index++] = arr[r++];
            }
        }
        while (l <=mid) {
            help[index++] = arr[l++];
        }
        while (r <= right) {
            help[index++] = arr[r++];
        }
        for (int i=0; i<help.length ; i++) {
            arr[left+i] = help[i];
        }
    }
}

5.快速排序

快速排序的思想就是先随机一个索引random，并将该位置的元素和最后一个元素进行交换，然后用一个下标pi来记录比该元素小的数，从左到右依次遍历，如果遇到比最后一个元素小的，就将pi++并与 pi++所指示的元素进行交换。最后在将最后一个元素换回来（此时pi所对应的的元素值就是最初random出的那个数），然后再对左边和右边分别进行递归

public class QuickSort {
    public int[] quickSort(int[] A, int n) {
        if (A== null || n <2) {
            return A;
        }
        process(A, 0, n-1);
        return A;
    }
    private void process(int[] arr, int left, int right) {
        if (left < right) {
            int random = left + (int) (Math.random() * (right - left + 1));
            swap(arr, random, right);
            int mid = partition(arr, left, right);
            process(arr, left, mid - 1);
            process(arr, mid + 1, right);
        }
    }
    private int partition(int[] arr, int left, int right) {
        int pi = left-1;
        int index = left;
        while (index <= right) {
            if (arr[index] <= arr[right]) {
                swap(arr, ++pi, index);
            }
            index++;
        }
        return pi;
    }
    private void swap(int[] arr, int indexA, int indexB) {
        int temp = arr[indexA];
        arr[indexA] = arr[indexB];
        arr[indexB] = temp;
    }
}

6.堆排序

堆排序的思想就是每次用未排序的元素构建完全二叉树的大根堆，然后将堆顶元素和最后一个元素进行交换，再次对剩下的元素构建大根堆，然后再交换，最后得到排序的结构。核心点就是大根堆的构建和交换

public class HeapSort {
    public int[] heapSort(int[] A, int n) {
        //构建大根堆
        for(int i=(n-1)/2;i>=0;i--){
            //依次对每个元素进行下沉
            sink(A,i,n-1);
        }
        int k=n-1;
        while(k>0){
            //置换出堆顶元素
            swap(A,0,k--);
            //将新换到堆顶的元素进行下沉
            sink(A,0,k);
        }
        return A;
    }
    public void sink(int [] arr, int i,int n){
        while(2*i+1<=n){
            int j=2*i+1;
            if(j<n&&arr[j+1]>arr[j]) j++;
            if(arr[i]>arr[j]) break;
            swap(arr,i,j);
            i=j;
        }
    }
    public void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

7.希尔排序

希尔排序其实是插入排序的变种，希尔排序的步长逐渐递减

public class ShellSort {
    public int[] shellSort(int[] A, int n) {
         int k=1;
         while(3*k<n) k=3*k+1;
         while(k>=1){
             for(int i=k;i<A.length;i++){
                 for(int j=i;j>=k;j-=k){
                     if(A[j]<A[j-k]){
                         int temp= A[j];
                         A[j]=A[j-k];
                         A[j-k]=temp;
                     }
                 }
             }
             k=k/3;
         }
        return A;
    }
}

8.计数排序和基数排序

这两种排序算法有其应用的局限性，都是基于分桶的思想
（1）计数排序
适合一段范围内的数据排序，比如有n个数进行排序，先求出最小值，再求出最大值，然后依据最小值和最大值分桶，相同的值在一个桶，最后将桶中的元素依次遍历出来即可

public class CountingSort {
    public int[] countingSort(int[] A, int n) {
        if(A == null || n <2) {
            return A;
        }
        int min = A[0];
        int max = A[0];
        for (int i =1 ;i < n; i++) {
            if (min > A[i]) {
                min = A[i];
            }
            if (max < A[i]) {
                max = A[i];
            }
        }
        int[] countArr = new int[max-min+1];
        for (int i=0; i< A.length; i++ ) {
            countArr[A[i]-min]++;
        }
        int index =0 ;
        for (int i=0 ; i<countArr.length; i++) {
            while (countArr[i]-- >0) {
               A[index++] = min+i;
            }
        }
        return A;
    }
}

（2）基数排序
适合对固定位数的数据进行排序，先对最低位进行排序，然后依次到最高位分别进行排序，如下给2000内的数据排序

public class RadixSort {
    public int[] radixSort(int[] A, int n) {
        int[][] buckets = new int[10][n];
        int base =1;
        for (int i=0;i<4; i++) {
            int[] count = new int[10];
            for (int j=0;j<n;j++) {
                int model = A[j]/base%10;
                //这里用Count来记录buckets下标为model行的元素的列下表（每个count记录了为当前model的元素个数）
                buckets[model][count[model]++] = A[j];
            }
            int index=0;
            for(int j=0;j<10;j++){
                for(int k=0;k<count[j];k++){
                    A[index++]=buckets[j][k];
                }
            }
            base*=10;
        }
        return A;
    }
}