MrainW's Home

All things come to those who wait!

0%

Sort

Quick sort

  • quick sort

<= p >=p

two part

11111111112,防止分布不均

average time complexity O(nlogn)

worst O(n^2)

space complexity O(1)

non stability

先整体有序,后局部有序

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
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers(int[] A) {
if (A == null || A.length == 0) {
return;
}
quickSort(A, 0, A.length - 1);
}

private void quickSort(int[] A, int start, int end) {
if (start >= end) {
return;
}

int left = start, right = end;
int pivot = A[(start + end) / 2];
//left <= right
//32145, 不存在交集,否则不断循环
//[12][2345]
while (left <= right) {
//1111111 A[left]<=pivot,全部归到左面,不均衡
while (left <= right && A[left] < pivot) {
left++;
}
while (left <= right && A[right] > pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
quickSort(A, start, right);
quickSort(A, left, end);
}
}

Merge sort

  • merge sort

worst O(nlogn)

space complexity O(n)

stability

先局部有序,后整体有序

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
public class Solution {
public void sortIntegers(int[] A) {
if (A == null || A.length == 0) {
return;
}
int[] temp = new int[A.length];
mergeSort(A, 0, A.length - 1, temp);
}

private void mergeSort(int[] A, int start, int end, int[] temp) {
if (start >= end) {
return;
}
mergeSort(A, start, (start + end) / 2, temp);
mergeSort(A, (start + end) / 2 + 1, end, temp);
merge(A, start, end, temp);
}

private void merge(int[] A, int start, int end, int[] temp) {
int middle = (start + end) / 2;
int leftIndex = start;
int rightIndex = middle + 1;
int index = start;
while (leftIndex <= middle && rightIndex <= end) {
if (A[leftIndex] <= A[rightIndex]) {
temp[index++] = A[leftIndex++];
} else {
temp[index++] = A[rightIndex++];
}
}
while (leftIndex <= middle) {
temp[index++] = A[leftIndex++];
}
while (rightIndex <= end) {
temp[index++] = A[rightIndex++];
}
for (int i = start; i <= end; i++) {
A[i] = temp[i];
}
}
}

Quick selection

  • kth largest element

O(n)

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
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
return -1;
}
return partition(nums, 0, nums.length - 1, nums.length - k);
}

private int partition(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[k];
}

int left = start, right = end;
int pivot = nums[(start + end) / 2];

while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
//start-right right-left left-end 三部分
if (k <= right) {
return partition(nums, start, right, k);
}
if (k >= left) {
return partition(nums, left, end, k);
}
return nums[k];
}

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

Welcome to my other publishing channels