LeetCode 912. 排序数组

题目描述

🔥 912. 排序数组

image-20220911002819655

思路分析

  1. 归并排序
  2. 快速排序
  3. 堆排序

参考代码

归并排序

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

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    public void merge(int[] nums, int left, int mid, int right) {
        int[] res = new int[right - left + 1];
        int p = 0, p1 = left, p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (nums[p1] < nums[p2]) {
                res[p] = nums[p1];
                p1++;
            } else {
                res[p] = nums[p2];
                p2++;
            }
            p++;
        }
        while (p1 <= mid) {
            res[p] = nums[p1];
            p1++;
            p++;
        }
        while (p2 <= right) {
            res[p] = nums[p2];
            p2++;
            p++;
        }
        System.arraycopy(res, 0, nums, left, res.length);
    }
}

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

func sortArray(nums []int) []int {
	return mergeSort(nums)
}

func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	mid := len(nums) / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])
	return merge(left, right)
}

func merge(nums1 []int, nums2 []int) []int {
	var res []int
	p1, p2 := 0, 0
	for p1 < len(nums1) && p2 < len(nums2) {
		if nums1[p1] < nums2[p2] {
			res = append(res, nums1[p1])
			p1++
		} else {
			res = append(res, nums2[p2])
			p2++
		}
	}
	res = append(res, nums1[p1:]...)
	res = append(res, nums2[p2:]...)
	return res
}

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

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	mergeSort(nums, 0, len(nums)-1)
	return nums
}

func mergeSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	mid := left + (right-left)/2
	mergeSort(nums, left, mid)
	mergeSort(nums, mid+1, right)
	merge(nums, left, mid, right)
}

func merge(nums []int, left, mid, right int) {
	var res []int
	p1, p2 := left, mid+1
	for p1 <= mid && p2 <= right {
		if nums[p1] < nums[p2] {
			res = append(res, nums[p1])
			p1++
		} else {
			res = append(res, nums[p2])
			p2++
		}
	}
	for p1 <= mid {
		res = append(res, nums[p1])
		p1++
	}
	for p2 <= right {
		res = append(res, nums[p2])
		p2++
	}
	for i := 0; i < len(res); i++ {
		nums[left+i] = res[i]
	}
}

快速排序

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

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    // 快速排序
    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int index = (int) (Math.random() * (right - left + 1)) + left;
        swap(nums, index, left);
        int i = left, j = right; // 左右指针
        int point = nums[left]; // 第一个元素作为基准点
        // i == j 的时候退出循环, 此时这个位置存放基准点
        while (i < j) {
            while (i < j && nums[j] > point) j--;
            if (i < j) nums[i++] = nums[j];
            while (i < j && nums[i] < point) i++;
            if (i < j) nums[j--] = nums[i];
        }
        nums[i] = point; // 或者 nums[j] = point, 此时 i == j, 基准点存放的位置
        quickSort(nums, left, i - 1); // 递归左半部分
        quickSort(nums, i + 1, right); // 递归右半部分
    }

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

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

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, left int, right int) {
	if left >= right {
		return
	}
	i, j := left, right
	point := nums[i]
	for i < j {
		for i < j && nums[j] > point {
			j--
		}
		if i < j {
			nums[i] = nums[j]
			i++
		}
		for i < j && nums[i] < point {
			i++
		}
		if i < j {
			nums[j] = nums[i]
			j--
		}
	}
	nums[i] = point
	quickSort(nums, left, i-1)
	quickSort(nums, i+1, right)
}

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

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	var res []int
	point := nums[0]
	var left, right []int

	for _, num := range nums[1:] {
		if num > point {
			right = append(right, num)
		} else {
			left = append(left, num)
		}
	}

	sortedLeft := sortArray(left)
	sortedRight := sortArray(right)

	res = append(res, sortedLeft...)
	res = append(res, point)
	res = append(res, sortedRight...)
	return res
}

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

func sortArray(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	rand.Seed(time.Now().Unix())
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	pointIndex := rand.Intn(right-left+1) + left
	nums[left], nums[pointIndex] = nums[pointIndex], nums[left]
	point := nums[left]
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= point {
			j--
		}
		if i < j {
			nums[i] = nums[j]
			i++
		}
		for i < j && nums[i] <= point {
			i++
		}
		if i < j {
			nums[j] = nums[i]
			j--
		}
	}
	nums[i] = point
	quickSort(nums, left, i-1)
	quickSort(nums, i+1, right)
}

堆排序

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

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        heapSort(nums);
        return nums;
    }

    // 堆排序
    private void heapSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            shiftHeap(nums, i, nums.length);
        }
        for (int j = nums.length - 1; j > 0; j--) {
            swap(nums, 0, j);
            shiftHeap(nums, 0, j);
        }
    }

    // 调整一个数组为大顶推(升序)
    private void shiftHeap(int[] nums, int k, int len) {
        while (2 * k + 1 < len) {
            int j = 2 * k + 1;
            if (j + 1 < len && nums[j + 1] > nums[j]) j++;
            if (nums[k] >= nums[j]) break;
            swap(nums, k, j);
            k = j;
        }
    }

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

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/03329404
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！