GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — leet-code/Java/QuickSort.java at master · awangdev/leet-code

Expand file tree

/

QuickSort.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
109 lines (94 loc) · 3.13 KB
/

QuickSort.java

Copy path

File metadata and controls

executable file
·
109 lines (94 loc) · 3.13 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
M
tags: Sort, Quick Sort
implement quick sort.
#### Quick Sort
- 首先partition. 返还一个partition的那个中间点的位置: 这个时候, 所有小于nums[partitionIndex] 都应该在 partitionIndex左边
- 然后劈开两半
- 前后各自 quick sort, recursively
- 注意：在partition里面, 比较的时候nums[start] < pivot, nums[end]>pivot, 如果写成了 <= 会 stack overflow.
- Time O(nlogn), Space: O(1)
```
/*
Quick Sort a array.
*/
public class Solution {
public void quickSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
dfs(nums, 0, nums.length - 1);
}
/**
Partition one side, and recursively partition(swaping).
Once one side finished, move on to partition && sorting the other side.
*/
private void dfs(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int partitionIndex = partition(nums, start, end);
dfs(nums, start, partitionIndex - 1);
dfs(nums, partitionIndex, end);
}
/**
Use two pointers: find the two points on left/rigth of the pivot that are startNum < pivot < endNum.
Swap them, and keep moving star++, end--.
This operation partition the array into 2 parts:
- numbers less than pivot (unsorted) on left of pivot
- numbers breater than pivot (unsorted) on right of pivot
*/
private int partition(int[] nums, int start, int end) {
int mid = start + (end - start) / 2;
int pivot = nums[mid];
while (start <= end) {
while (start <= end && nums[start] < pivot) {
start++;
}
while (start <= end && nums[end] > pivot) {
end--;
}
if (start <= end) {
swap(nums, start, end);
start++;
end--;
}
}
return start;
}
private void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
private void printArray(int[] nums, String str) {
System.out.print(str);
if (nums == null || nums.length == 0) {
System.out.println();
return;
}
for (int num : nums) {
System.out.print(num + ", ");
}
System.out.println();
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println("Implement and test quick sort");
int[] array = {5,3,2,7,5,4,1,1,2,9,5,3, -1};
sol.quickSort(array);
sol.printArray(array, "Return: ");
array = null;
sol.quickSort(array);
sol.printArray(array, "Return Empty: ");
array = new int[]{ - 1, 2};
sol.quickSort(array);
sol.printArray(array, "Return: ");
array = new int[]{ 1,1,1,1,1};
sol.quickSort(array);
sol.printArray(array, "Return: ");
array = new int[]{ 19,8,7,6,5,4,3,2,1};
sol.quickSort(array);
sol.printArray(array, "Return: ");
}
}
```
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.