Sort

排序

---

均未考虑边界条件

冒泡

比较相邻的，第一个大，就交换。$n^2​$复杂度

public void bubblie(int[] a){
    int length=a.length;
    for(int i=length-1;i>=0;i++){
        for(int j=0;j<i;j++){
            if(a[j+1]<a[j]){
                int temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
			            
        }
    }
    
}

选择

找最大，放最右边。然后继续$n^2$

public void select(int[] a,int length){
    if(length==1)return ;
    int max=0;
    for(int i=0;i<length;i++){
        if(a[i]>a[max]){
            max=i;
        }
    }
    swap(a,length-1,max);
    select(a,length-1);
}

插入

$n^2$ ,前n个已经排序，第n+1个，依次与前面的相比较。放到合适位置。

public void insert(int[] a){
    if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        
}

希尔排序

增量，分组，魅族插入排序，然后减小增量。$nlogn​$

public void shell(int[] a){ 
int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
}

归并排序

分成n/2 子序列。分别采用归并。最后合并。$nlogn$ 稳定,需要额外空间。

public static int[] MergeSort(int[] array) {
       if (array.length < 2) return array;
       int mid = array.length / 2;
       int[] left = Arrays.copyOfRange(array, 0, mid);
       int[] right = Arrays.copyOfRange(array, mid, array.length);
       return merge(MergeSort(left), MergeSort(right));
   }
   /**
    * 归并排序——将两段排序好的数组结合成一个排序数组
    *
    * @param left
    * @param right
    * @return
    */
   public static int[] merge(int[] left, int[] right) {
       int[] result = new int[left.length + right.length];
       for (int index = 0, i = 0, j = 0; index < result.length; index++) {
           if (i >= left.length)
               result[index] = right[j++];
           else if (j >= right.length)
               result[index] = left[i++];
           else if (left[i] > right[j])
               result[index] = right[j++];
           else
               result[index] = left[i++];
       }
       return result;
   }

快排

通常，枢纽元不应该选择第一个或者最后一个，int pivot = (int) (start + Math.random() * (end - start + 1));因为如果数组是排好序的，最坏的情况下，将会是$n^2$的，

while循环中的两个while循环不要加=号，会溢出边界

public void quicksort(int[] a,int start,int end){
    if(start>=end)return;
    int pivot=a[end];
    int left=start,right=end-1;
    while(left<right){
        
        while(a[left]<pivot)
            left++;
        while(a[right]>pivot){
            right--;
        }
        if(left<right){
            swap(a,left,right);
            left++;
            right--;
        }
    }
    swap(a,left,end);
    quicksort(a,start,left-1);
    quicksort(a,left+1,end);
}

###　堆排序

平均$nlogn$ ，

public void sort() {
    /*
     *  第一步：将数组堆化
     *  beginIndex = 第一个非叶子节点。
     *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
     *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
     */
    int len = arr.length - 1;
    int beginIndex = (len - 1) >> 1;
    for (int i = beginIndex; i >= 0; i--)
        maxHeapify(i, len);
    /*
     * 第二步：对堆化数据排序
     * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
     * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
     * 直至未排序的堆长度为 0。
     */
    for (int i = len; i > 0; i--) {
        swap(0, i);
        maxHeapify(0, i - 1);
    }
}

private void swap(int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/**
 * 调整索引为 index 处的数据，使其符合堆的特性。
 *
 * @param index 需要堆化处理的数据的索引
 * @param len 未排序的堆（数组）的长度
 */
private void maxHeapify(int index, int len) {
    int li = (index << 1) + 1; // 左子节点索引
    int ri = li + 1;           // 右子节点索引
    int cMax = li;             // 子节点值最大索引，默认左子节点。
    if (li > len) return;      // 左子节点索引超出计算范围，直接返回。
    if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
        cMax = ri;
    if (arr[cMax] > arr[index]) {
        swap(cMax, index);      // 如果父节点被子节点调换，
        maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
    }
}

基数

数字的位数不能差太多，按照数字的位数排序

public void radix(int[] a){
    //先求位数
    int max=0;
    for(int i=0;i<a.length;i++){
        if（max<a[i]){
            max=a[i];
        }
    }
    int maxDigit=1;
    while(max/10>0){
        maxDigit++;
        max=max/10;
    }
    int[][] buckets=new int[10][a.length];
    int base=10;
    for(int i=0;i<maxDigit;i++){
        int bkt=new int[10];//存放第I个的数量
        for(int j=0;j<a.length;j++){
            int b=(a[j]%base)/(base/10);
            buckets[b][bkt[b]]=a[j];//
            bkt[b]++;
        }
        int x=0;
        for(int k=0;k<10;k++){
            for(l=0;l<b[k];l++){
                a[x++]=buckets[b][p];//按照顺序取出
            }
        }
    }
}

桶排序

计数排序的通用版，一个是利用数字，一个是利用hash。分到有限个桶里，每个桶再分别排序(可能用其他的排序方法)。

private int indexFor(int a, int min, int step) {
	return (a - min) / step;
}

public void bucketSort(int[] arr) {

	int max = arr[0], min = arr[0];
	for (int a : arr) {
		if (max < a)
			max = a;
		if (min > a)
			min = a;
	}
	// 該值也可根據實際情況選擇
	int bucketNum = max / 10 - min / 10 + 1;
	List buckList = new ArrayList<List<Integer>>();
	// create bucket
	for (int i = 1; i <= bucketNum; i++) {
		buckList.add(new ArrayList<Integer>());
	}
	// push into the bucket
	for (int i = 0; i < arr.length; i++) {
		int index = indexFor(arr[i], min, 10);
		((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
	}
	ArrayList<Integer> bucket = null;
	int index = 0;
	for (int i = 0; i < bucketNum; i++) {
		bucket = (ArrayList<Integer>) buckList.get(i);
		insertSort(bucket);
		for (int k : bucket) {
			arr[index++] = k;
		}
	}

}

// 把桶內元素插入排序
private void insertSort(List<Integer> bucket) {
	for (int i = 1; i < bucket.size(); i++) {
		int temp = bucket.get(i);
		int j = i - 1;
		for (; j >= 0 && bucket.get(j) > temp; j--) {
			bucket.set(j + 1, bucket.get(j));
		}
		bucket.set(j + 1, temp);
	}
}

计数排序

用数组下标来表示数字大小，也就是hash的想法。

public class CountingSort {
    public void count(int[] a){
        int min=findMin(a);
        int max=findMax(a);
        int[] rs=new int[max-min+1];
        for(int i=0;i<a.length;i++){
            rs[a[i]-min]++;
        }
        int j=0;
        for(int i=0;i<rs.length;i++){
            while(rs[i]>0){
                a[j++]=i;
            }
        }
    }
}