1. 插入类排序
直接插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int temp = nums[i];
int j = i-1;
while (j >= 0 && nums[j] > temp) {
nums[j+1] = nums[j];
--j;
}
nums[j+1] = temp;
}
return nums;
}
};
折半插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int temp = nums[i];
int left = 0, right = i;
while (left < right) {
int mid = left + (right-left)/2;
if (nums[mid] < temp)
left = mid + 1;
else
right = mid;
}
right = i-1;
while (right >= left ) {
nums[right+1] = nums[right];
--right;
}
nums[left] = temp;
}
return nums;
}
};
希尔排序
略
2. 交换类排序
1. 冒泡
1
2
3
4
5
6
7
8
9
10
11
12
class Solution3 {
public:
vector<int> sortArray(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
for (int j = nums.size()-1; j > i ; --j) {
if (nums[j] < nums[j-1])
swap(nums[j], nums[j-1]);
}
}
return nums;
}
};
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
25
26
27
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
doback(nums, 0, nums.size()-1);
return nums;
}
void doback(vector<int> &nums, int left, int right) {
if (left >= right)
return;
int index = doTo2(nums, left, right);
doback(nums, left, index-1);
doback(nums, index+1, right);
}
int doTo2(vector<int> &nums, int left, int right) {
int temp = nums[left];
while (left < right) {
while (left < right && nums[right] >= temp)
-- right;
nums[left] = nums[right];
while (left < right && nums[left] < temp)
++ left;
nums[right] = nums[left];
}
nums[left] = temp;
return left;
}
};