
#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:202112112
# author:yang
 
import random
from randomList import randomList
import sort
 
def bubbleSort(iList):
    iLen = len(iList)
    for i in range(iLen):
        for j in range(0,iLen-i-1):
            if iList[j] > iList[j+1]:
                iList[j],iList[j+1] = iList[j+1],iList[j]
 
    return iList
 
if __name__ == "__main__":
   iList = randomList(10)
   print("iList1:",iList)
   bubbleSort(iList)
   print("iList2:",iList)


void bubbleSort() {
 
	int iList[] = { 5,4,7,8,2,9,10,4,0,3};
	int len = sizeof(iList) / sizeof(int);
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < len - i - 1; j++) {
			if (iList[j] > iList[j+1]) {
 
				int temp = iList[j+1];
				iList[j+1] = iList[j];
				iList[j] = temp;
			}
		}
	}
 
	for (int i = 0; i < len; i++) {
		cout << iList[i] << " ";
	}
	cout << endl;
}

拓展：timeit()用法

python中的timeit（）方法，它用于获取代码的执行时间。该库将代码语句默认运行一百万次，并提供从集合中花费的最短时间，可以用来检查代码的性能。

语法：

timeit.timeit(stmt, setup,timer, number)

参数：

stmt：这将采用您要测量其执行时间的代码。默认值为“pass”。

setup：这将包含需要在stmt之前执行的设置详细信息。这个参数可以将stmt的环境传进去。比如各种import和参数什么的。默认值为“ pass”。

timer：它将具有计时器值，timeit（）已经设置了默认值，我们可以忽略它。

number：stmt将按照此处给出的编号执行。默认值为1000000。

注：

要使用timeit（），我们需要导入模块，如下：

import timeit

另外需要补充一点是，如果你想直接 stmt 那里执行函数。可以把函数申明在当前文件中，然后在 stmt = ‘func()’ 执行函数。然后使用 setup = ‘from __main__ import func’ 即可，如果要import 多个需要使用 setup = from __main__ import func; import simplejson'

4.归并排序

归并排序（Merge Sort）是一种典型的递归法排序。它把复杂的排序过程分解成一个简单的合并子序列的过程。至于怎么得到这个子序列，就得自己调用自己了。

原理

归并排序首先要做的就是将数列分成左右两部分（最好是等分），然后将左、右两个子数列排序完毕后再合并到一起就成了一个有序数列。左、右两个子数列怎么变成有序数列呢？那就回头调用自
己，再把子数列分成左、右两部分，直到将所有的子数列的长度分为1为止。然后把子子数列排序完毕后合并成子数列……有点像那个著名的故事，山上有座山，山里有座庙，庙里有两个和尚……。和尚讲故事是无穷无尽的，幸运的是数列的长度即使再大也不会是无尽的。所以当子子子……序列分到不可再分割的时候（最小的序列长度为1时），就可以返回开始合并数列了。逐步合并子子子子……数列，到最后就得到了一个新的有序数列。

第一次分组

第二次分组

经过三次分组，已经将所有的子子子数列都变成了长度为1的数列。现在可以确定这些长度为1的数列必定是有序数列了，然后开始反向合并这些数列。

第一次合并

这里还需要考虑left和right长度不一致的情况。先合并数列[3]、[5]以及[9]、[4]。

第二次合并

第三次合并

归并排序完毕。经过3次合并，最终得到了一个有序数列。归并排序的时间复杂度是 O ( n Log n） )。

代码


#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
 
from randomList import randomList
import timeit
 
def mergeSort(iList):
    if len(iList) <= 1:
        return iList
    middle = len(iList)//2
    left,right = iList[0:middle],iList[middle:]
    return mergeList(mergeSort(left),mergeSort(right))
 
def mergeList(left,right):
    """合并序列"""
    mList = []
    while left and right:
        if left[0] >= right[0]:
            mList.append(right.pop(0))
        else:
            mList.append(left.pop(0))
            
    while left:
        mList.append(left.pop(0))
    while right:
        mList.append(right.pop(0))
    return mList   
    
if __name__ == "__main__":
    iList = randomList(10)
    print(iList)
    print(mergeSort(iList))
    # print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))

5.快速排序

快速排序（Quick Sort）算法也是一种递归排序。

原理

以列表中的任意一个数为基准（一般选择列表中的第一个数），将列表分为左、右（前、后）两个子列表：左边子列表的数要比基准数小，右边子列表的数要比基准数大。然后继续把左边子列表和右边子列表按同样的方法继续分解、比较，一直到分无可分为止。然后按照左边子列表（比基准数小）+基准数+右边子列表（比基准数大）的方式连接起来。最后得到一个有序的数列。

以数列[7,3,5,1,9,4]为例。

第一次分组

以“7”为基准，比7小的分在左边的子数列中，比7大的分在右边的子数列中。

此时左边的子序列有4个数[3, 5, 1, 4]，还需要继续分组。右边的子序列中只有一个数9，不需要再分了。第二次只需要将左边的部分分组排序就可以了。

第二次分组

左边的子序列还剩下[3, 5, 1, 4]，现在以第一个数3为基准数，将后面部分的[5, 1, 4]分成两部分。同样还是比基准数（3）小的放到左边子序列，比基准数（3）大的放到右边子序列。

数分组完毕后。只要按照一定的顺序重新组合起来就可以了。组合很简单，就是小的数（左边部分）+中间数（基准数）+大的数（右边部分）。

第一次合并

将子序列合并，具体规则是left + [base] + right。这里需要稍微注意一下，left和right都是序列（列表），而base部分是单独的一个数，所以需要将它序列化。

第二次合并

第三次合并

经过3次分组、合并后，得到了有序数列。快速排序的时间复杂度最坏的情况下是 O ( n ^2 )。

代码（python&cpp）


#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
 
from randomList import randomList
import timeit
 
def quickSort(iList):
    if len(iList) <= 1:
        return iList
    left = []
    right = []
    for i in iList[1:]:
        if i <= iList[0]:
            left.append(i)
        else:
            right.append(i)
    return quickSort(left) + [iList[0]] + quickSort(right)
        
 
if __name__ == "__main__":
    iList = randomList(10)
    print(iList)
    print(quickSort(iList))
    # print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))

注：此方法速度快。

6.计数排序

计数排序（Counting Sort）算法是一种比较特殊的算法，因为它不是一个基于比较的算法。将两个数进行比较，将大的数放后面、小的数放前面，这样的算法都是基于比较的算法。

原理

它采用了一个巧妙的方法，选择一个数为基数，然后统计整个数列中有多少个数比基数小。如果有 n 个数比基数小，那么基数就放到新数列的第n +1的位置上（rList[n]）。以数列[7, 3, 5, 1, 9, 4]为例，首先要做的是先创建一个与[7, 3, 5, 1, 9, 4]相同长度的空数列。

第一个数的位置

第二个数的位置

第三个数的位置

依次类推

将所有的数字都插入到新数列后，排序就完成了。计数排序的时间复杂度是 O ( n + k )，其中 k 是整数的范围。

代码（python&cpp）


#!/user/bin/env/python3
#-*-conding:utf-8 -*-
# data:20211210
# author:yang
 
from randomList import randomList
import timeit
 
def countingSort(iList):
    if len(iList) <= 1:
        return iList
    iLen = len(iList)
    rList = [None]*iLen
    for i in range(iLen):
        small = 0   # 比基数小的
        same = 0    # 与基数相等的
        for j in range(iLen):
            if iList[j] < iList[i]:
                small += 1
            elif iList[j] == iList[i]:  # 相同的数
                same += 1
        for k in range(small,small+same):
            rList[k] = iList[i]
    return rList
           
 
if __name__ == "__main__":
    iList = randomList(10)
    print(iList)
    print(countingSort(iList))
    # print(timeit.timeit("selectionSort(iList)","from __main__ import selectionSort,iList",number = 1))

总结

从表格上来看，排序100次用时最少，速度最快的应该是快速排序。果然是名副其实。选择排序的速度与快速排序相差无几。用时最多、速度最慢的是插入排序，其次就是冒泡排序。当然，根据输入数列的不同，这个排名可能会有所变动。

参考

图解leetcode初级算法（python版）--胡松涛

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/693492