常用排序算法比较与分析一、常用排序算法简述下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。
依据待排序的问题大小(记录数量 n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【排序】、【外排序】。
排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。
外排序：待排序记录的数量很大，以致存一次不能容纳全部记录，在排序过程中还需要对外存进行访问的排序过程。
先了解一下常见排序算法的分类关系(见图1-1)图1-1 常见排序算法二、排序相关算法2.1 插入排序核心思想：将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。
2.1.1 直接插入排序核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、… 数据元素的值进行顺序比较，通过这种线性搜索的方法找到第i个数据元素的插入位置，并且原来位置的数据元素顺序后移，直到全部排好顺序。
直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。
Python源代码：1.#-------------------------直接插入排序--------------------------------2.def insert_sort(data_list):3.#遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始4.for x in range(1, len(data_list)):5.#将该元素与已排序好的前序数组依次比较，如果该元素小，则交换6.#range(x-1,-1,-1):从x-1倒序循环到07.for i in range(x-1, -1, -1):8.#判断：如果符合条件则交换9.if data_list[i] > data_list[i+1]:10.temp= data_list[i+1]11.data_list[i+1] = data_list[i]12.data_list[i] = temp2.1.2 希尔排序核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。
Python源代码：1.#-------------------------希尔排序-------------------------------2.def insert_shell(data_list):3.#初始化step值，此处利用序列长度的一半为其赋值4.group= int(len(data_list)/2)5.#第一层循环：依次改变group值对列表进行分组6.while group> 0:7.#下面：利用直接插入排序的思想对分组数据进行排序8.#range(group,len(data_list)):从group开始9.for i in range(group, len(data_list)):10.#range(x-group,-1,-group):从x-group开始与选定元素开始倒序比较，每个比较元素之间间隔group11.for j in range(i-group, -1, -group):12.#如果该组当中两个元素满足交换条件，则进行交换13.if data_list[j] > data_list[j+group]:14.temp= data_list[j+group]15.data_list[j+group] = data_list[j]16.data_list[j] = temp17.#while循环条件折半18.group= int(group/ 2)2.2 选择排序核心思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。
2.2.1 直接选择排序核心思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素和最后一个元素比较为止。
根据其基本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个和当前元素相等的元素后面，则它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O(n2)，空间复杂度为O(l)。
Python源代码：1.#-------------------------直接选择排序-------------------------------2.def select_sort(data_list):3.#依次遍历序列中的每一个元素4.for i in range(0, len(data_list)):5.#将当前位置的元素定义此轮循环当中的最小值6.minimum = data_list[i]7.#将该元素与剩下的元素依次比较寻找最小元素8.for j in range(i+1, len(data_list)):9.if data_list[j] < minimum:10.temp= data_list[j];11.data_list[j] = minimum;12.minimum = temp13.#将比较后得到的真正的最小值赋值给当前位置14.data_list[i] = minimum2.2.2 堆排序堆排序时对直接选择排序的一种有效改进。
核心思想：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。
完成堆排序需要执行两个动作：建堆和堆的调整，如此反复进行。
堆排序有可能会使得两个相同值的元素位置发生互换，所以是不稳定的，其平均时间复杂度为0(nlog2n)，空间复杂度为O(l)。
Python源代码：1.#-------------------------堆排序--------------------------------2.#**********获取左右叶子节点**********3.def LEFT(i):4.return2*i + 15.6.def RIGHT(i):7.return2*i + 28.9.#********** 调整大顶堆**********10.#data_list:待调整序列length: 序列长度i:需要调整的结点11.def adjust_max_heap(data_list,length,i):12.#定义一个int值保存当前序列最大值的下标rgest = i14.#执行循环操作：两个任务：1 寻找最大值的下标；2.最大值与父节点交换15.while 1:16.#获得序列左右叶子节点的下标17.left, right= LEFT(i), RIGHT(i)18.#当左叶子节点的下标小于序列长度并且左叶子节点的值大于父节点时，将左叶子节点的下标赋值给largest19.if (left< length) and(data_list[left] > data_list[i]):rgest = left21.#print('左叶子节点')22.else:rgest = i24.#当右叶子节点的下标小于序列长度并且右叶子节点的值大于父节点时，将右叶子节点的下标值赋值给largest25.if (right< length) and(data_list[right] > data_list[largest]):rgest = right27.#print('右叶子节点')28.#如果largest不等于i 说明当前的父节点不是最大值，需要交换值29.if (largest != i):30.temp= data_list[i]31.data_list[i] = data_list[largest]32.data_list[largest] = temp33.i = largest34.#print(largest)35.continue36.else:37.break38.39.#********** 建立大顶堆**********40.def build_max_heap(data_list):41.length = len(data_list)42.for x in range(int((length-1)/2),-1,-1):43.adjust_max_heap(data_list,length,x)44.45.#********** 堆排序**********46.def heap_sort(data_list):47.#先建立大顶堆，保证最大值位于根节点；并且父节点的值大于叶子结点48.build_max_heap(data_list)49.#i：当前堆中序列的长度.初始化为序列的长度50.i = len(data_list)51.#执行循环：1. 每次取出堆顶元素置于序列的最后(len-1,len-2,len-3...)52.# 2. 调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度53.while i > 0:54.temp= data_list[i-1]55.data_list[i-1] = data_list[0]56.data_list[0] = temp57.#堆中序列长度减158.i = i-159.#调整大顶堆60.adjust_max_heap(data_list, i, 0)2.3交换排序核心思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比较各自的关键码，如果是逆序，则交换这两个数据元素，直到该序列数据元素有序为止。
2.3.1 冒泡排序核心思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原则，将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整，让较重的元素往下沉，较轻的往上冒。
根据基本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否则保持不变，所以冒泡排序时稳定的。
时间复杂度为平方阶O(n2)，空间复杂度为O(l)。