文章目录
- 1. 题目
- 2. 解题
- 2.1 插入排序
- 2.2 冒泡排序
- 2.3 选择排序
- 2.4 希尔排序
- 2.5 归并排序
- 2.6 快速排序
- 2.7 堆排序
- 2.8 计数排序
- 2.9 桶排序
- 2.10 基数排序
- 3. 复杂度表
1. 题目
给你一个整数数组 nums，将该数组升序排列。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12示例 1： 输入：nums = [5,2,3,1] 输出：[1,2,3,5] 示例 2： 输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 提示： 1 <= nums.length <= 50000 -50000 <= nums[i] <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
基础的排序算法，写一遍复习一下。
参考我的博客：
10种C++排序算法
快速排序quicksort算法优化
快速排序quicksort算法细节优化（一次申请内存/无额外内存排序）
2.1 插入排序
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution { public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j; for(i = 0; i < arr.size(); ++i) { for(j = i; j > 0; --j) { if(arr[j-1] > arr[j]) swap(arr[j-1],arr[j]); else break; } } return arr; } };
9 / 10 个通过测试用例，超时
2.2 冒泡排序
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution { public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j; bool arrSorted = false; for(i = 0; i < arr.size(); ++i) { arrSorted = true; for(j = 1; j <= arr.size()-1-i; ++j) { if(arr[j-1] > arr[j]) { swap(arr[j-1],arr[j]); arrSorted = false; } } if(arrSorted) break; } return arr; } };
超时
2.3 选择排序
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution { //选择 public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j, minIdx = 0; for(i = 0; i < arr.size()-1; ++i) { minIdx = i; for(j = i+1; j < arr.size(); ++j) { if(arr[minIdx] > arr[j]) minIdx = j; } swap(arr[i],arr[minIdx]); } return arr; } };
超时
2.4 希尔排序
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution { //希尔 public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j, gap = 1; for(gap = arr.size()/2; gap > 0; gap /= 2) { for(i = gap; i < arr.size(); ++i) { for(j = i; j-gap >= 0 && arr[j-gap]>arr[j]; j -= gap) swap(arr[j-gap],arr[j]); } } return arr; } };
72 ms 15.8 MB
2.5 归并排序
复制代码
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
40class Solution { //归并 vector<int> temp; public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; temp.resize(arr.size()); mergeSort(arr,0, arr.size()-1); return arr; } void mergeSort(vector<int>& arr, int l, int r) { if(l == r) return; int mid = l+((r-l)>>1); mergeSort(arr,l,mid); mergeSort(arr,mid+1,r); merge(arr,l,mid,r); } void merge(vector<int>& arr, int l, int mid, int r) { int i = l, j = mid+1, k = 0; while(i <= mid && j <= r) { if(arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while(i <= mid) temp[k++] = arr[i++]; while(j <= r) temp[k++] = arr[j++]; for(k = 0, i = l; i <= r; ++i,++k) arr[i] = temp[k]; } };
52 ms 16 MB
2.6 快速排序
复制代码
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
56class Solution { //快排 public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; qsort(arr,0, arr.size()-1); return arr; } void qsort(vector<int>& arr, int l, int r) { if(l >= r) return; int Pl = l, Pr = l; partition(arr,l,r,Pl,Pr); qsort(arr,l,Pl-1); qsort(arr,Pr+1,r); } void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr) { selectMid(arr,l,r); int P = arr[l]; int i = l, j = r; while(i < j) { while(i < j && P < arr[j])//没有等于号，哨兵都在左侧 j--; swap(arr[i], arr[j]); while(i < j && arr[i] <= P) i++; swap(arr[i], arr[j]); } Pl = Pr = i; for(i = i-1; i >= l; --i)//聚集左侧与哨兵相等的到中间 { if(arr[i] == P) { Pl--; swap(arr[i], arr[Pl]); } } } void selectMid(vector<int>& arr, int l, int r) { int mid = l+((r-l)>>1); if(arr[mid] > arr[r]) swap(arr[mid],arr[r]); if(arr[l] > arr[r]) swap(arr[l], arr[r]); if(arr[mid] > arr[l]) swap(arr[mid], arr[l]); } };
52 ms 15.6 MB
96 ms 15.8 MB（删除聚集哨兵操作后的用时）
2.7 堆排序
复制代码
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
37class Solution { //堆排序, 建堆（升序建大堆，降序建小堆） public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; for(int i = arr.size()/2-1; i >= 0; --i) adjust(arr,i,arr.size());//建堆 for(int i = arr.size()-1; i >= 0; --i) { swap(arr[i],arr[0]); adjust(arr,0,i); } return arr; } void adjust(vector<int>& arr, int i, int len) { int lchild = 2*i+1, rchild = 2*i+2, maxIdx = i; while(lchild < len) { if(lchild < len && arr[lchild] > arr[maxIdx]) maxIdx = lchild; if(rchild < len && arr[rchild] > arr[maxIdx]) maxIdx = rchild; if(maxIdx != i) { swap(arr[i],arr[maxIdx]); lchild = 2*maxIdx+1; rchild = lchild+1; i = maxIdx; } else break; } } };
72 ms 15.8 MB
2.8 计数排序
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution { //计数排序 public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j = 0, min, max; min = max = arr[0]; for(i = 1; i < arr.size(); ++i) { min = arr[i] < min ? arr[i] : min; max = arr[i] > max ? arr[i] : max; } const int N = max-min+1; vector<int> count(N,0); for(i = 0; i < arr.size(); ++i) count[arr[i]-min]++; for(i = 0; i < N; ++i) { while(count[i]--) arr[j++] = i+min; } return arr; } };
36 ms 16.1 MB
2.9 桶排序
- 数据装桶，桶内快排
复制代码
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
85class Solution { //桶排序 public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, j = 0, min, max; min = max = arr[0]; for(i = 1; i < arr.size(); ++i) { min = arr[i] < min ? arr[i] : min; max = arr[i] > max ? arr[i] : max; } if(min == max) return arr; int div = 1000;//桶个数 int space = (max-min)/div+1; vector<int> temp(arr.size()); vector<int> bucketsize(div,0); vector<int> bucketPos(div,0); for(i = 0; i < arr.size(); ++i) bucketsize[(arr[i]-min)/space]++; bucketPos[0] = bucketsize[0]; for(i = 1; i < div; ++i) bucketPos[i] += bucketPos[i-1] + bucketsize[i];//桶结束位置的下一个 for(i = 0; i < arr.size(); ++i) temp[--bucketPos[(arr[i]-min)/space]] = arr[i]; for(i = 0; i < div; ++i) { if(bucketsize[i] > 1) { qsort(temp,bucketPos[i],bucketPos[i]+bucketsize[i]-1); } } for(i = 0; i < arr.size(); ++i) arr[i] = temp[i]; return arr; } void qsort(vector<int>& arr, int l, int r) { if(l >= r) return; int Pl = l, Pr = l; partition(arr,l,r,Pl,Pr); qsort(arr,l,Pl-1); qsort(arr,Pr+1,r); } void partition(vector<int>& arr, int l, int r, int& Pl, int& Pr) { selectMid(arr,l,r); int P = arr[l]; int i = l, j = r; while(i < j) { while(i < j && P < arr[j])//没有等于号，哨兵都在左侧 j--; swap(arr[i], arr[j]); while(i < j && arr[i] <= P) i++; swap(arr[i], arr[j]); } Pl = Pr = i; for(i = i-1; i >= l; --i) { if(arr[i] == P) { Pl--; swap(arr[i], arr[Pl]); } } } void selectMid(vector<int>& arr, int l, int r) { int mid = l+((r-l)>>1); if(arr[mid] > arr[r]) swap(arr[mid],arr[r]); if(arr[l] > arr[r]) swap(arr[l], arr[r]); if(arr[mid] > arr[l]) swap(arr[mid], arr[l]); } };
40 ms 16.3 MB
2.10 基数排序
- 注意处理负数，被坑了，负数%后越界，window不报错尽然。。
复制代码
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
36class Solution { //基数排序 vector<int> temp; public: vector<int> sortArray(vector<int>& arr) { if(arr.size() <= 1) return arr; int i, max = INT_MIN; long exp; temp.resize(arr.size()); for(i = 0; i < arr.size(); ++i) { arr[i] += 50000;//便于负数处理 max = arr[i] > max ? arr[i] : max; } for(exp = 1; max/exp > 0; exp*=10) radix_sort(arr,exp); for(i = 0; i < arr.size(); ++i) arr[i] -= 50000;//还原 return arr; } void radix_sort(vector<int>& arr, long exp) { vector<int> bucketsize(10,0); int i; for(i = 0; i < arr.size(); ++i) bucketsize[(arr[i]/exp)%10]++; for(i = 1; i < 10; ++i) bucketsize[i] += bucketsize[i-1];//桶最后一个位置+1 for(i = arr.size()-1; i >= 0; --i) temp[--bucketsize[(arr[i]/exp)%10]] = arr[i]; for(i = 0; i < arr.size(); ++i) arr[i] = temp[i]; } };
56 ms 16 MB
3. 复杂度表
图片参考 https://leetcode-cn.com/problems/sort-an-array/solution/shi-er-chong-pai-xu-suan-fa-bao-ni-man-yi-dai-gift/
r 为排序数字的范围，d 是数字总位数，k 是数字总个数
最后
以上就是现实服饰最近收集整理的关于LeetCode 912. 排序数组（10种排序）的全部内容，更多相关LeetCode内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复