左神算法-基础课-02-代码

Posted on | In , , ,

快速排序

1
2
3
4
5
6
public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return;
    }
    quickSort(arr, 0, arr.length-1);
}
1
2
3
4
5
6
7
8
public static void quickSort(int[] arr, int l, int r) {
    if (l < r){
        swap(arr, l + (int)(Math.random() * (r - l + 1)), r);   // 随机找一个数作为分割的数字；
        int[] p = partition(arr,l, r);  // 返回less部分后一位和more部分前一位组成的数组；
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] partition(int[] arr, int l, int r) {    // 荷兰国旗式的partition
    int less = l - 1;
    int more = r;
    while (l < more){
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l ++;
        }
    }
    swap(arr, more, r);
    return new int[] {less + 1, more};
}
1
2
3
4
5
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void heapSort(int[] arr) {
    if (arr == null || arr.length<2){
        return;
    }
    for (int i = 0; i <arr.length ; i++) {
        heapInsert(arr, i);
    }
    int size = arr.length;
    swap(arr, 0, --size);
    while (size > 0){
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }
}
1
2
3
4
5
6
public static void heapInsert(int[] arr, int index) {
    while(arr[index] > arr[(index-1)/2]){
        swap(arr, index, (index-1)/2);
        index = (index-1)/2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void heapify(int[] arr, int index, int size) {
    int left = 2 * index + 1;
    while (left < size){
        int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[index] < arr[largest] ? largest : index;
        if (largest == index){
            break;
        }
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}
1
2
3
4
5
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}