Sort Algorithm

整理几个排序算法的实现。包括归并排序,快速排序与堆排序等。

归并排序

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

import math
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result

def mergesort(arr):
length = len(arr)
if length <= 1:
return arr
middle = math.floor(length/2)
left = mergesort(arr[:middle])
right = mergesort(arr[middle:])
return merge(left,right)

if __name__ == '__main__':
arr = [4,7,8,3,5,9]
print(mergesort(arr))

快速排序

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
# 这边提供partition的两种版本,以及一个用stack替代递归的。
def quickSort(arr, left, right):
if left < right:
partitionIndex = partition2(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr

def partition(arr, left, right):
pivot = arr[left]
leftmark = left+1
rightmark = right
done = False
while not done:
while arr[rightmark] >= pivot and rightmark >= leftmark:
rightmark -= 1
while arr[leftmark] <= pivot and leftmark <= rightmark:
leftmark += 1
if rightmark < leftmark:
done = True
else:
#swap(arr, leftmark, rightmark)
arr[leftmark], arr[rightmark] = arr[rightmark], arr[leftmark]

arr[left], arr[rightmark] = arr[rightmark], arr[left]
return rightmark

def partition2(arr, left, right):
pivot = arr[right]
place = left-1
for search in range(left, right):
if arr[search] <= pivot:
place += 1
arr[place], arr[search] = arr[search], arr[place]

arr[place+1], arr[right] = arr[right], arr[place+1]
return place+1

def quickSort_Stack(array, left, right):
if left >= right:
return
stack = []
stack.append(left)
stack.append(right)
while stack:
low = stack.pop(0)
#print("low:{}".format(low))
high = stack.pop(0)
#print("high:{}".format(high))
if high-low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i+1], array[high] = array[high], array[i+1]
stack.extend([low,i,i+2,high])
#print("array:")
#print(array)

return array

test = [52,312,54,7,3,2]
print(quickSort(test, 0, len(test)-1))

单链表的快速排序

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
class Node:  
def __init__(self, data):
self.data = data
self.next = None


def swap(a, b): # 交换函数,因为有可能自己和自己交换,所以有个if
if a.data != b.data: # 这里用了值交换,必要的话可以用链表节点交换
tmp = a.data
a.data = b.data
b.data = tmp


def quick_sort(begin, end):
# 为空或只有一个元素直接返回
if (begin is None) or (begin == end):
return
i = begin # 使用i, j分别代表标志位应该交换的位置和循环变量
j = begin.next
# 下面这一部分是关键,
while j is not None:
if j.data <= begin.data: # 比较当前数是否小于标志数
i = i.next # 交换i向后移和当前数交换
swap(i, j)
j = j.next
swap(i, begin) # 最后交换标志位和i
# i也就是这样一个位置,左侧大于标志,右侧小于标志
# 递归
quick_sort(begin, i)
quick_sort(i.next, end)

堆排序

参考自

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
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
//建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子节点指标在范围内才做比较
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小,选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕,直接跳出函数
return;
else { //否则交换父子内容再继续子节点和孙节点比较
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}

void heap_sort(int arr[], int len) {
//初始化,i从最后一个父节点开始调整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先将第一个元素和已经排好的元素前一位做交换,再从新调整(刚调整的元素之前的元素),直到排序完毕
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}