首页 > 代码库 > 数据结构中常见的排序算法

数据结构中常见的排序算法

2024-07-06 18:15:32   225人阅读

  • 选择排序

i从0开始，默认本趟最小的位置min_index为i，若第min_index大于第i+1、i+2直到n-1，则修改min_index为i+1、i+2...n-1，若min_index不等于i，则交换位置。重复n-1次，完成排序。
比较操作为n(n-1)/2次，即O(n^2)；交换操作介于0和(n-1)次，即O(n)；赋值操作介于0和3(n-1)次，即O(n)。主要优点在于数据的移动，如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

1 def selection_sort(data):
2     for i in range(len(data)):
3         min_index = i
4         for j in range(i+1,len(data)):
5             if data[min_index] > data[j]:
6                 min_index = j
7         if min_index <> i:
8             data[i],data[min_index] = data[min_index],data[i]
View Code
  • 堆排序

将序列调整成堆，交换堆顶元素与最后一个节点元素，将最后一个节点剔除出堆，再将剩下序列调整成堆，然后再交换堆顶元素与最后一个节点元素...

 1 def heap_adjust(data,s,m):
 2     if 2*s > m:
 3         return
 4     temp = s-1
 5     if data[2*s-1] > data[temp]:
 6         temp = 2*s-1
 7     if 2*s <= m-1 and data[2*s] > data[temp]:
 8         temp = 2*s
 9     if temp <> s-1:
10         data[s-1],data[temp] = data[temp],data[s-1]
11         heap_adjust(data,temp+1,m)
12 
13 def heap_sort(data):
14     for i in range(len(data)/2,0,-1):
15         heap_adjust(data,i,len(data))
16     data[0],data[-1] = data[-1],data[0]
17     for n in range(len(data)-1,1,-1):
18         heap_adjust(data,1,n)
19         data[0],data[n-1] = data[n-1],data[0]
View Code
  • 插入排序

i从1开始，待插入tmp为第i，若tmp小于第i-1、i-2...0，则第i-1、i-2...0移动到第i，i-1...1，tmp插入第i-1、i-2...0。此时，第0...第i有序，第i+1...n-1无序。重复n-1次，完成排序。

1 def insertion_sort(data):
2     for i in range(1,len(data)):
3         tmp = data[i]
4         j = i-1
5         while data[j] > tmp and j >= 0:
6             data[j+1] = data[j]
7             j = j-1
8         if j <> i-1:
9             data[j+1] = tmp
View Code
  • 希尔排序

将序列分割为若干相隔increament的子序列，对各个子序列进行插入排序；再选择一个更小的increment，再将序列分割为多个子序列进行排序...直到increment为1，最终序列有序。
O(n的1.5次方)，不稳定排序。把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，比直接从无序到有序移动的次数少，提高效率。

 1 def shell_sort(data,step=None):
 2     if step == None:
 3         step = len(data)//2
 4     for i in range(0,step):
 5         subdata =http://www.mamicode.com/ data[i:len(data):step]
 6         insertion_sort(subdata)
 7         data[i:len(data):step] = subdata
 8     if step <> 1:
 9         step = step//2
10         shell_sort(data,step)
View Code
  • 冒泡排序

i从0开始，若第i大于第i+1，则交换位置，直到第n-i-2和第n-i-1。此时，第n-i-1为本趟最大。重复n-1次，即n-i-1为0时，完成排序。
o(n^2)，稳定排序，适合规模比较小数据。

1 def bubble_sort(data):
2     for i in range(len(data)):
3         for j in range(len(data)-i-1):
4             if data[j] > data[j+1]:
5                 data[j],data[j+1] = data[j+1],data[j]
View Code
  • 快速排序

1. 选择序列的第1个元素作为基准standard，比standard大的放在基准右边，比standard小的放在基准左边，最终移动standard，形成standard前和standard后的两个子序列；
2 递归地选择子序列的第一个元素作为子序列的子基准standard，划分子子序列。

 1 def quick_sort(data,low=0,high=None):
 2     if high==None:
 3         high = len(data)-1
 4     if low < high:
 5         standard,left,right = data[low],low,high
 6         while left < right:
 7             while data[right] > standard and left < right:
 8                 right = right-1
 9             if left < right:
10                 data[left] = data[right]
11                 left = left+1
12             while data[left] <= standard and left < right:
13                 left = left+1
14             if left < right:
15                 data[right] = data[left]
16         data[left] = standard
17         quick_sort(data,low,left-1)
18         quick_sort(data,left+1,high)
View Code
  • 性能对比
 1 import random,datetime,copy
 2 
 3 def sort_perform(sort,data):
 4     sort_data =http://www.mamicode.com/ copy.deepcopy(data)
 5     t1 = datetime.datetime.now()
 6     sort(sort_data)
 7     t2 = datetime.datetime.now()
 8     print sort.__name__, ‘\t‘, t2-t1
 9 
10 if __name__ == ‘__main__‘:
11     data = http://www.mamicode.com/[random.randint(0,65535) for i in range(3000)]
12     sort_perform(selection_sort,data)
13     sort_perform(heap_sort,data)
14     sort_perform(insertion_sort,data)
15     sort_perform(shell_sort,data)
16     sort_perform(bubble_sort,data)
17     sort_perform(quick_sort,data)
View Code

从[0,65535)中随机抽取3000个数（有重复），测试结果为：

　　selection_sort　　　　0:00:00.629048
　　heap_sort　　　　　　0:00:00.055195
　　insertion_sort　　　　0:00:00.730729
　　shell_sort　　　　　　0:00:00.035422
　　bubble_sort　　　　　0:00:01.510431
　　quick_sort　　　　　　0:00:00.017847


联系
我们