常见排序算法有快速排序、插入排序、冒泡排序、归并排序、希尔排序
可以在leetcode这道题里面实验所有的方法https://leetcode-cn.com/problems/sort-an-array

快速排序

时间复杂度O(nlgn), 空间复杂度O(n), 不稳定排序

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(nums):

def partition(start, end, nums):
if start >= end:
return
p = nums[start]
left = start
right = end
while left < right:
while nums[right] >= p and left < right:
right -= 1
while nums[left] <= p and left < right:
left += 1
nums[right], nums[left] = nums[left], nums[right]
nums[start], nums[left] = nums[left], nums[start]
partition(start, left - 1, nums)
partition(left + 1, end, nums)
partition(0, len(nums)-1, nums)

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort(nums) {
function partition(start, end, nums) {
if (start >= end) return;
let p = nums[start], l = start, r = end, t;
while (l < r) {
while (l < r && nums[r] >= p) {
r -= 1;
}
while (l < r && nums[l] <= p) {
l += 1;
}
t = nums[l]; // 交换
nums[l] = nums[r];
nums[r] = t;
}
t = nums[start]; // 交换中轴
nums[start] = nums[l];
nums[l] = t;
partition(start, l - 1, nums);
partition(l + 1, end, nums);
}
partition(0, nums.length - 1, nums);
}

插入排序

时间复杂度O(n^2), 空间复杂度O(1), 稳定排序

python实现

1
2
3
4
5
6
7
8
9
10
def insertSort(nums):
start = 0
end = len(nums)
for i in range(start, end):
j = i-1
temp = nums[i]
while temp < nums[j] and j >= 0: # 往后移,直到有可以插入的空位
nums[j+1] = nums[j]
j -= 1
nums[j+1] = temp

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort(nums) {
let len = nums.length;
let temp;
for (let i = 0; i < len; i++) {
temp = nums[i];
j = i - 1;
while (j >= 0 && temp < nums[j]) {
nums[j+1] = nums[j];
j -= 1;
}
nums[j+1] = temp;
}
}

希尔排序

非稳定排序算法,时间复杂度O(nlg2n), 空间复杂度O(1)
将插入排序的对所有元素进行比较,改为将全部元素划分为几个区域,使得元素能够一次性的向正确位置跨越一大步。然后算法将步数越变越小,在这个过程中,数据是几乎排好序的,所以插入排序选择可能位置的时间很少。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
def shell_sort(nums):
end = len(nums)
inc = len(nums) // 2 # 步进
while inc > 0:
for i in range(inc, end): # 从inc, inc+1, inc+2遍历
temp = nums[i]
j = i - inc
while temp < nums[j] and j >= 0:
nums[j+inc] = nums[j]
j -= inc
nums[j+inc] = temp
inc //= 2

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function shellSort(nums) {
let step = Math.floor(nums.length / 2);
let len = nums.length;
while (step > 0) {
for (let i = step; i < len; i += step) {
temp = nums[i];
j = i - step;
while (j >= 0 && temp < nums[j]) {
nums[j+step] = nums[j];
j -= step;
}
nums[j+step] = temp;
}
step = Math.floor(step / 2)
}
}

冒泡排序

时间复杂度O(n^2),空间复杂度O(1),稳定排序
python实现

1
2
3
4
5
def bubble_sort(nums):
for i in range(len(nums)):
for j in range(0, len(nums)-1): # 交互大小相反的元素
if nums[j] > nums[j+1]:
nums[j+1], nums[j] = nums[j], nums[j+1]

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(nums) {
let len = nums.length;
let temp;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (nums[j] > nums[j+1]) {
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}

归并排序

时间复杂度O(nlgn), 空间复杂度O(n),稳定排序

python实现

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
def merge_sort(nums):

def merge(left, mid, right, nums):
i = left
j = mid+1
temp = []
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp.append(nums[i])
i += 1
else:
temp.append(nums[j])
j += 1
if i <= mid:
temp.extend(nums[i: mid+1])
if j <= right:
temp.extend(nums[j: right+1])
nums[left: right+1] = temp

def divide(start, end, nums): # 拆分
if start < end:
mid = (start + end) // 2
divide(start, mid, nums)
divide(mid+1, end, nums)
merge(start, mid, end, nums) # 归并

divide(0, len(nums)-1, nums)

javascript实现

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
function mergeSort(nums) {
function merge(left, mid, right, nums) {
let i = left,
j = mid + 1,
temp = new Array;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
temp.push(nums[i]);
i += 1;
} else {
temp.push(nums[j]);
j += 1;
}
}
while (i <= mid) {
temp.push(nums[i]);
i += 1;
}
while (j <= right) {
temp.push(nums[j]);
j += 1;
}
nums.splice(left, temp.length, ...temp); // 替换为以merge数组
}

function divide(start, end, nums) {
if (start < end) {
let mid = Math.floor((start+end)/2);
divide(start, mid, nums);
divide(mid+1, end, nums);
merge(start, mid, end, nums);
}
}

divide(0, nums.length-1, nums);
}

堆排序

时间复杂度O(nlogn),空间复杂度O(1),不稳定算法。

其中最关键的是heapify操作,让二叉树大根堆化,也就是父节点要比任意子节点大。排序操作也就是在不同范围内找到堆顶,也就是最大值,下一次大根堆化不把上次的堆顶计算进来。

python实现

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
def heapify(nums, start, end):
# 构建当前子树为大根堆
parent = start
while parent < end:
son = parent * 2 + 1
if son > end:
return
if son < end and nums[son+1] > nums[son]:
son += 1
if nums[parent] > nums[son]:
return
nums[parent], nums[son] = nums[son], nums[parent]
parent = son


def heap_sort(nums):
parent = len(nums)//2 - 1 # 最后一个父节点
end = len(nums) - 1
for i in range(parent, -1, -1):
# 将每个子树都大根化
heapify(nums, i, end)
print(nums)
for i in range(len(nums)-1, -1, -1):
nums[i], nums[0] = nums[0], nums[i]
print(nums)
heapify(nums, 0, i-1)

javascript实现

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
function heapSort(nums) {
let len = nums.length;

function heapify(start, end) {
let parent = start;
let son;
while (parent < end) {
son = 2 * parent + 1;
if (son > end) return;
if (son < end && nums[son] < nums[son + 1]) {
son += 1
}
if (nums[parent] > nums[son]) {
return;
}
let t = nums[parent]
nums[parent] = nums[son]
nums[son] = t
parent = son;
}
}

let lastParent = Math.floor(nums.length / 2) + 1;
for (let i = lastParent; i >= 0; i--) {
heapify(i, len - 1);
}
for (let i = len - 1; i > 0; i--) {
let t = nums[0];
nums[0] = nums[i];
nums[i] = t;
heapify(0, i - 1);
}
return nums
}

选择排序

时间复杂度O(n^2),空间复杂度O(1),不稳定

每次选择最小的值,放入当前位置。

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function selectSort(nums) {
let len = nums.length;
for (let i = 0; i < len; i++) {
let temp = i;
for (let j = i+1; j < len; j++) {
if (nums[temp] > nums[j]) {
temp = j;
}
}
[nums[temp], nums[i]] = [nums[i], nums[temp]]
}
return nums
}