数据结构——排序算法_yujieyu12345678

数据结构——排序算法

一共有6种排序算法，分别为：冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序

冒泡排序

冒泡排序就是比较相邻两个元素，若左边元素大于右边元素则换序，这样第一轮换序完之后最大的就会到最后一位，然后再进行第二轮，第二轮只用比较前n-1个即可，n个循环之后排序完成。

python代码如下：

def bubble_sort(a):
	n = len(a)
	for j in range(n):
		count = 0
		for i in range(n-j-1):
			if a[i] > a[i+1]:
				a[i], a[i+1] = a[i+1], a[i]
				count += 1
			else:
				continue
		if count == 0:
			break
1
2
3
4
5
6
7
8
9
10
11
12

选择排序

选择排序就是先找到列表中最小的元素放在第一位，然后再找剩余元素中最小的放在第二位，以此类推即可完成排序。

python代码如下：

def selection_sort(a):
	n = len(a)
	for i in range(n-1):
		min_index = i
		# 利用循环找到最小值的下标 min_index
		for j in range(i+1,n):
			if a[j] < a[min_index]:
				min_index = j
		if min_index != i:
			a[i], a[min_index] = a[min_index], a[i]
1
2
3
4
5
6
7
8
9
10

插入排序

插入排序是每次从后面选择一个元素，将其与前面的相比较，放入正确的位置，例如[7,3,9], 首先将3与7比较，将其放在7的前面变成[3,7,9]，然后将9与3,7比较，放在最后，完成排序[3,7,9]。

python代码如下:

def insert_sort(a):
	n = len(a)
	for i in range(1,n):
		for j in range(i,0,-1):
			if a[j] < a[j-1]:
				a[j], a[j-1] = a[j-1], a[j]
1
2
3
4
5
6

希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法终止。

python代码如下:

def shell_sort(a):
	n = len(a)
	gap = n//2
	while gap > 0:
		for i in range(gap,n):
			while i >= gap:
				if a[i] < a[i-gap]:
					a[i], a[i-gap] = a[i-gap], a[i]
				i -= gap
		gap = gap // 2
1
2
3
4
5
6
7
8
9
10

快速排序

快速排序是每次选取第一个元素，将小于它的放在左边，大于它的放在右边，例如[5,2,18,10,93]，对于5来说可将列表分为[2, 5, 18,10,93]，然后分别对[2], 及[18,10,93]进行快速排序，直到排序完成。

步骤：

1. 从数列中挑出一个元素，称为"基准"；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

python代码如下:

def quick_sort(a, start, end):
	pivot = a[start]
	low = start
	high = end
	while low < high:
		while low < high and a[high] >= pivot:
			high -= 1
		a[low] = a[high]
		while low < high and a[low] < pivot:
			low += 1
		a[high] = a[low]
	a[low] = pivot
	quick_sort(a, start, low-1)
	quick_sort(a, low+1, end)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

归并排序

归并排序的思想就是先递归分解数组，将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

python代码如下:

def merge_sort(a):
	n = len(a)
	if n == 1:
		return a
	else:
		mid = n//2
		left = merge_sort(a[:mid])
		right = merge_sort(a[mid:])
		return merge(left, right)

def merge(left, right):
	l = 0
	r = 0
	newlist = []
	while l < len(left) and r < len(right):
		if left[l] < right[r]:
			newlist.append(left[l])
			l += 1
		else:
			newlist.append(right[r])
			r += 1
	newlist += left[l:]
	newlist += right[r:]
	return newlist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

常见排序的时间复杂度及稳定性

二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

python代码如下:

# 非递归版本
def binary_search(alist, item):
	first = 0
	last = len(alist)-1
	while first <= last:
		mid = (first+last)//2
		if alist[mid] == item:
			return True
		elif alist[mid] < item:
			first = mid + 1
		elif alist[mid] > item:
			last = mid -1
	return False
# 递归版本
def binary_search_2(alist, item):
	if len(alist) == 1:
		return alist[0] == item
	else:
		mid = len(alist)//2
		if alist[mid] == item:
			return True
		elif alist[mid] > item:
			return binary_search_2(alist[:mid], item)
		else:
			return binary_search_2(alist[mid:], item)

# 注意二分查找的算法复杂度为O(nlogn)
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