排序算法(Java版)

public static void bubbleSort(int[] arr) {
    if(arr.length == null || arr.length == 0) return;
    
    int len = arr.length;
    for(int i = 0; i < len-1; i++) {
        for(int j = 0; j < len-i-1; j++) {
            if(arr[j]>arr[j+1]) swap(arr, j, j+1);
        }
    }
}

public static void selectSort(int[] arr) {
    if(arr.length == null || arr.length == 0) return new int[];
    int len = arr.length;
    for(int i = 0; i < len-1; i++) {
        minIndex = i;
        for(int j = i+1; j < len; j++) {
            if(arr[j]< arr[minIndex]) minIndex = j;
        }
        swap(arr, i, minIndex);
    }
}

public static void insertSort(int[] arr) {
    if(arr == null || arr.length == 0) return new int[];
    
    for(int i = 1; i < len; i++) {
        int current = arr[i];
        int preIndex = i-1;
        while(preIndex>=0 && arr[preIndex]>arr[i]) {
            arr[preIndex+1] = arr[preIndex];//后移
            preIndex--;
        }
        arr[preIndex+1]=current;
    }
}
// 重写版，更简洁
public static void insertSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    for (int i = 1, len = arr.length; i < len; i++) {
        for (int j=i; j > 0 && arr[j]<arr[j-1]; j--) {
            swap(arr, j, j-1);
        }
    }
}

public class Shell {
    public static void shellSort(int[] a) {
        //升序排列
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h + 1;
        while(h>0) {
            for(int i = h; i < N; i++) {
                for(int j = i; j >=h && a[j]<a[j-h]; j -= h) {
                    swap(a, j, j-h);
                }
            }
            h = h/3;
        }
    }
}

public static void mergeSort(int[] arr, int left, int right) {
    sort(arr, left, right);
}

public static void sort(int[] arr, int left, int right) {
    if(left>=right) return;

    int mid = (left+right)/2;
    sort(arr, left, mid);
    sort(arr, mid+1, right);
    merge(arr, left, right);

}

public static void merge(int[] arr, int left, int right) {
    int[] result = new int[arr.length];
    int mid = (left+right)/2;
    int leftIndex = left, rightIndex = mid+1, i = left;
    System.out.println("left:"+left+", right: "+right);
    for(int j = 0; j <= right; j++) {
        System.out.printf("%d\t", arr[j]);
    }
    System.out.printf("\n");
    while(leftIndex <= mid && rightIndex <= right) {
        if(arr[leftIndex] < arr[rightIndex]) {
            result[i++] = arr[leftIndex++];
        } else {
            result[i++] = arr[rightIndex++];
        }
    }

    while(leftIndex <= mid) {
        result[i++] = arr[leftIndex++];
    }

    while(rightIndex <= right) {
        result[i++] = arr[rightIndex++];
    }
    //对arr进行重新复制
    //for(int j = left; j <= right; j++) {
    //    arr[j] = result[j];
    //}
    System.arraycopy(result,left, arr, left, right-left+1);

    for(int j = 0; j <= right; j++) {
        System.out.printf("%d\t", arr[j]);
    }
    System.out.printf("\n");
}

public static void quickSort(int[] arr, int left, int right) {
    if(left>=right) return;
    int partIndex = partion(arr, left, right);
    quickSort(arr, left, partIndex-1);
    quickSort(arr, partIndex+1, right);
}

public static int partion(int[] arr, int left, int right) {
    int pivot = arr[right];//每次以最后一个元素作为基准元素
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j]<pivot) {
            swap(arr, i++, j);
        }
    }
    swap(arr, i, right);
    return i;
}

public class Heap<T extends Comparable<T>> {
	//实现一个最大堆
    private T[] heap;
    private int N = 0;

    public Heap(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;//说明位置i的数值小于位置j的数值，之后进行交换
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }
    
    public void swim(int k) {
        //上浮操作，不断跟父节点进行比较即可
        while(k>1 && less(k/2, k)) {
            swap(k, k/2);
            k = k/2;
        }
    }
	
    private void sink(int k) {
        //下沉操作，不断跟子节点比较
        while(2*k<=N) {//不超过元素的个数
            int j = 2*k;//左节点
            if(j < N&&less(j, j+1)) {//左节点小于右节点
            	j++;
            }
            if(less(j, k)) break;//大于子节点
            swap(k, j);
            k = j;
        }
    }
    
    private void insert(Comparable v) {
        heap[++N] = (T) v;//加入到数组尾，并增加数组个数N
        swim(N);//上浮到合适的位置
    }
    //删除最大元素
    private T deleteMax() {
        T max = heap[1];
        swap(1, N--);//将尾子节点跟堆顶交换
        head[N+1]=null;
        sink(1);//将堆顶下沉
        return max;
    }
}