快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void quickSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int i = partition(nums, l, r);
    //i为分界值 i左边的都是小于nums[i] 右边的都是大于的
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

int partition(int[] nums, int l, int r) {
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) {
            j--; //找到小于当前选定值的数的位置
        }
        while (i < j && nums[i] <= nums[l]) {
            i++; //找到大于当前选定值的数的位置
        }
        swap(nums, i, j); //交换 把小于的数换到左边 大于的数换到右边
    } //一次循环后 所有小于的数都放到了左边 所有大于的数都放到了右边
    //由于第一个j--循环 此时nums[i]的值是小于nums[l]
    //而i左边的都是小于nums[l],右边的都是大于nums[l]的
    //故此i位置应该放置的数应该是nums[l] 而nums[i]又恰好小于nums[l] 故交换i、l位置的值
    swap(nums, i, l);
    return i;
}

void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums, j, j - 1);
            } else {
                break;
            }
        }
    }
}
void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public void heapSort(int[] nums){
    //数组范围
    int len = nums.length - 1;
    //倒数第一个非叶子节点,作为第一个起始构建堆的下标
    int index = nums.length/2 - 1;
    //开始先构建堆
    for (int i = index; i >= 0; i--) {
        maxHeapify(nums, i, len);
    }
	
    //取堆顶的元素,放到最后面(移出堆,不在参与堆的构建),将最后面的挪到前面,再次构建堆,一直循环,每次得到剩余元素的最大值放在最后.
    for (int i = len; i > 0; i--) {
        swap(nums, 0, i);
        maxHeapify(nums, 0, i-1);
    }
}

public void maxHeapify(int[] nums, int index, int len){
    //index节点的左孩子和右孩子
    int left = 2*index + 1;
    int right = left + 1;
    //默认把左节点当最大的子节点
    int max = left;
    //左孩子下标越界
    if(left > len){
        return;
    }
    //判断右孩子的值并更新最大子节点
    if (right <= len && nums[right] > nums[left]) {
        max = right;
    }
    //把索引节点及子节点的最大值放在该子树顶部
    if(nums[max] > nums[index]){
        swap(nums, max, index);
        //如果更换了需要对调换的子节点字数进行堆排
        maxHeapify(nums, max, len);
    }
}

public void swap(int[] nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}


@Test
public void heapSort(){
    int[] nums = {3,2,1,4,2,5,1,6};
    heapSort(nums);
    for (int num : nums) {
        System.out.print(num + " ");
    }
    System.out.println();
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
private void mergeSort(int[] nums, int left, int right){
    if(left < right){
        int mid = left + ((right - left) >> 1);
        //左边归并排序，使得左子序列有序
        mergeSort(nums, left, mid);
        //右边归并排序，使得右子序列有序
        mergeSort(nums, mid+1, right);
        //将两个有序子数组合并操作
        merge(nums, left, mid, right);
    }
}

//合并
private void merge(int[] nums, int left, int mid, int right){
    int[] tmp = new int[right - left + 1]; //临时存放合并后有序数组
    int i = left, j = mid + 1;
    int k = 0; //临时数组指针
    while(i <= mid && j <= right){
        if(nums[i] <= nums[j]){
            tmp[k++] = nums[i++];
        }else{
            tmp[k++] = nums[j++];
        }
    }
    //将左边剩余元素填充进tmp中
    while(i <= mid){
        tmp[k++] = nums[i++];
    }
    //将右序列剩余元素填充进tmp中
    while(j <= right){
        tmp[k++] = nums[j++];
    }
    k = 0;
    //将temp中的元素全部拷贝到原数组中
    while(left <= right){
        nums[left++] = tmp[k++];
    }
}