首页 > 代码库 > 常见的几种算法排序
常见的几种算法排序
算法定义
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
一个算法应该具有以下七个重要的特征：
①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；②确切性(Definiteness)：算法的每一步骤必须有确切的定义；③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；⑥高效性(High efficiency)：执行速度快，占用资源少；⑦健壮性(Robustness)：对数据响应正确。
时间复杂度
计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间,时间复杂度常用大O符号（大O符号（Big O notation）
是用于描述函数渐进行为的数学符号；大O，简而言之可以认为它的含义是“order of”（大约是）
详细请见：http://www.cnblogs.com/alex3714/articles/5910253.html
http://www.cnblogs.com/alex3714/articles/5474411.html
常见排序
名称 | 复杂度 | 说明 | 备注 |
冒泡排序 | O(N*N) | 将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮 |
|
插入排序 Insertion sort | O(N*N) | 逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置 | 起初，已经排序的元素序列为空 |
选择排序 | O(N*N) | 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。 |
|
快速排序 Quick Sort | O(n *log2(n)) | 先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。 |
|
堆排序HeapSort | O(n *log2(n)) | 利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。 | 近似完全二叉树 |
希尔排序 SHELL | O(n1+￡) 0<￡<1 | 选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1. |
|
箱排序 | O(n) | 设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。 | 分配排序的一种：通过" 分配 " 和 " 收集 " 过程来实现排序。
|
一、冒泡排序
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
思路：
相邻两个值进行比较，将较大的值放在右侧，依次比较！
data_set = [9, 1, 22, 31, 45, 3, 6, 2, 11]# 第一种# for j in range(len(data_set)):# for i in range(len(data_set) - j - 1):# if data_set[i] > data_set[i+1]:## tmp = data_set[i]# data_set[i] = data_set[i+1]# data_set[i+1] = tmp# # data_set[i], data_set[i+1] = data_set[i+1], data_set[i] # 可以把上面三行代码简化成一句# print(data_set)# print(data_set)# 第二种count = len(data_set)for i in range(0, count): for j in range(i + 1, count): if data_set[i] > data_set[j]: data_set[i], data_set[j] = data_set[j], data_set[i]print(data_set)
时间复杂度说明看下他的代码复杂度会随着N的增大而成指数型增长，并且根据判断他时间复杂度为Ο(n2)
二、插入排序
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中
思路：
一个列表默认分为左侧为排序好的，我们拿第一个元素举例，他左边的全是排序好的，他右侧是没有排序好的，如果右侧的元素小于左侧排序好的列表的元素就把他插入到合适的位置
data_list = [34, 45, 7, 89, 43, 2, 6, 4, 12, -9, 34, 88, ]# 第一种：# for i in range(len(data_list)):# while i > 0 and data_list[i] < data_list[i - 1]:# tmp = data_list[i]# data_list[i] = data_list[i-1] # 如果while条件成立把当前的值替换成他的上个值# data_list[i - 1] = tmp# i -= 1 # 当上面的条件不成立时# print(data_list)# print(data_list)# 第二种：# for i in range(1, len(data_list)):# key = data_list[i]# for j in range(i-1, -1, -1):# if data_list[j] > key:# data_list[j + 1] = data_list[j]# data_list[j] = key# print(data_list)# 第三种count = len(data_list)for i in range(1, count): key = data_list[i] j = i - 1 while j >= 0: if data_list[j] > key: data_list[j + 1] = data_list[j] data_list[j] = key j -= 1print(data_list)
三、选择排序
基本思想：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
思路：
第一次，从列表最左边开始元素为array[0]，往右循环，从右边元素中找到小于array[0]的元素进行交换，直到右边循环完之后。
第二次，左边第一个元素现在是最小的了，就从array[1],和剩下的array[1:-1]内进行对比，依次进行对比！
对比：
选择排序和冒泡排序的区别就是，冒泡排序是相邻的两两做对比，但是选择排序是左侧的“对比元素”和右侧的列表内值做对比！
data_list = [34, 45, 7, 89, 43, 2, 6, 4, 12, -9, 34, 88, ]# 第一种# for k in range(len(data_list)):# set_len_index = k# for i in range(k, len(data_list)):# if data_list[i] < data_list[set_len_index]:# set_len_index = i# tmp = data_list[set_len_index]# data_list[set_len_index] = data_list[k]# data_list[k] = tmp# print(data_list)s# print(data_list)# 第二种count = len(data_list)for i in range(0, count): min = i # 假设默认第一个值最小 for j in range(i + 1, count): if data_list[min] > data_list[j]: min = j # 如果找到更小的，记录更小的元素的下标 data_list[min], data_list[i] = data_list[i], data_list[min]print(data_list)
四、快速排序
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，
所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，
多个相同的值的相对位置也许会在算法结束时产生变动.他的时间复杂度是：O(nlogn) ~Ο(n2)
排序示例：
假设用户输入了如下数组：
创建变量i=0（指向第一个数据）[i所在位置红色小旗子], j=5(指向最后一个数据)[j所在位置蓝色小旗子], k=6(赋值为第一个数据的值)。
i=0 j=3 k=6
i=2 j=3 k=6
如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。
然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，
需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
data_list = [35, 45, 7, 89, 43, 2, 6, 4, 12, -9, 34, 88, 6, ]def quick_sort(data_list, left, right): if left >= right: return data_list key = data_list[left] low = left high = right while left < right: while left < right and data_list[right] >= key: right -= 1 data_list[left] = data_list[right] while left < right and data_list[left] <= key: left += 1 data_list[right] = data_list[left] data_list[right] = key quick_sort(data_list, low, left - 1) quick_sort(data_list, left + 1, high) return data_listif __name__ == ‘__main__‘: quick_sort(data_list, 0, len(data_list)-1) print(data_list)
def quick_sort(array, left, right): ‘‘‘ :param array: :param left: 列表的第一个索引 :param right: 列表最后一个元素的索引 :return: ‘‘‘ if left >= right: return low = left high = right key = array[low] # 第一个值 while low < high: # 只要左右未遇见 while low < high and array[high] > key: # 找到列表右边比key大的值为止 high -= 1 array[low] = array[high] # 此时直接 把key(array[low]) 跟 比它大的array[high]进行交换 array[high] = key while low < high and array[low] <= key: # 找到key左边比key大的值，这里为何是<=而不是<呢？你要思考。。。 low += 1 array[high] = array[low] # 找到了左边比k大的值 ,把array[high](此时应该刚存成了key) 跟这个比key大的array[low]进行调换 array[low] = key quick_sort(array, left, low-1) # 最后用同样的方式对分出来的左边的小组进行同上的做法 quick_sort(array, low+1, right) # 用同样的方式对分出来的右边的小组进行同上的做法if __name__ == ‘__main__‘: array = [96, 14, 10, 9, 6, 99, 16, 5, 1, 3, 2, 4, 1, -123, -876, 13, 26, 18, 2, 45, 34, 23, 1, 7, 3, 22, 19, 2] print("before sort:", array) quick_sort(array, 0, len(array)-1) print("-------final -------") print(array)后续更新...
常见的几种算法排序