一、排序简介
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
稳定性：冒泡直接归并。
二、冒泡排序
参考冒泡排序
冒泡排序算法的运作如下：
- 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
对于图片上的直观理解，建议看冒泡排序中代码后面的图片。
需要注意的地方：
- 1、因为是需要比较两个元素，所以在索引时用到了alist[i+1]的情况，因此在为了不让index超出范围，应该让for循环中的passnum-1。
- 2、每一次循环，最大的元素都已经排到列表最后了，下一次循环就可以减短列表长度了，因此在循环结束以后需要加上passnum -= 1。
代码实现：
def bubbleSort(alist):
#构造一个倒序列表，从而限制了每次遍历一次以后的循环长度
passnum = len(alist)
while passnum > 0:
for i in range(passnum-1):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
passnum -= 1
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
按理说，按照这个代码，最好的情况也应该跟选择排序一样，时间复杂度同样是O(n2)，为什么这里却说“最好情况下，冒泡排序的时间复杂度是O(n)”?
因为可以改进呀~
参考冒泡排序最佳情况的时间复杂度，为什么是O(n)
其中代码中，加了一步：如果对某一个元素执行操作以后发现并没有进行交换操作，说明已经排序完毕，就不再执行排序操作了。
代码实现：
public void bubbleSort(int arr[]) {
boolean didSwap;
for(int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;
for(int j = 0; j < len - i - 1; j++) {
if(arr[j + 1] < arr[j]) {
swap(arr, j, j + 1);
didSwap = true;
}
}
if(didSwap == false)
return;
}
}
三、选择排序
选择排序也是一种简单直观的排序算法。（以从小到大的排序为例。）
1、初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；
2、然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
具体操作图片见 选择排序
选择排序与冒泡排序的区别：
- 冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小元素放到合适的位置
- 选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
由于选择排序需要记住的是当前最大元素的位置，因此需要设置一个index_max的变量并令初始值为0 ，接下来就要比较每个元素，循环一次，就能得到最大值的index了。
接下来就是交换元素的操作。
另外，这里的for循环中passnum应该保持不变。
代码实现：
def selectionSort(alist):
#构造一个倒序列表，从而限制了每次遍历一次以后的循环长度
passnum = len(alist)
while passnum > 0:
index_max = 0
for i in range(passnum):
if alist[i]>alist[index_max]:
index_max = i
temp = alist[passnum-1]
alist[passnum-1] = alist[index_max]
alist[index_max] = temp
passnum -= 1
alist = [54,26,93,17,77,31,44,55,20]
selectSort(alist)
print(alist)
四、插入排序
插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。
如下图：
对于一个列表[5,4,2,10,7],在用插入排序到达[2,4,5,10,7]的结果时，对于最后一个元素7，从后向前进行比较，比10小，就与10交换位置，直到前面一位的元素比7小为止。
注意，在从后向前扫描的过程中，需要不断地交换两个元素的位置。
从图像上直观理解插入排序
伪代码：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素cur-1（已排序）大于新元素cur，则替换二者位置，让小的元素往前进
- 重复步骤3，直到找到已排序的元素cur-1小于或者等于新元素cur的位置
- 将新元素插入到该位置后
- 重复步骤2~5
代码：
按照伪代码，此处需要加两个循环：
- 1、一个是for循环，按照插入排序的思想，需要对列表中每个元素执行一次插入操作，从左到右。
- 2、一个是while循环，执行比较与换位操作。
若是前一个元素nums[cur-1]大于当前元素nums[cur]，则二者互换位置
1、while循环结束条件：
当cur指向的元素为0即列表开头时，停止循环
当cur元素小于等于第cur-1的元素时，目的已经达到，执行break语句。
2、while循环改变语句：
每循环一次，cur指针就要减1，与前面的前面的元素进行比较
代码实现：
def Insertionsort(nums):
for i in range(len(nums)):
cur = i
while cur >= 1:
if nums[cur-1] > nums[cur]:
temp = nums[cur - 1]
nums[cur - 1] = nums[cur]
nums[cur] = temp
cur -= 1
else:
break
return nums
print(Insertionsort([6, 5, 4, 1, 8, 7, 2, 4 ]))
五、希尔排序
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
于是，我们提出一个想法，（针对第二点）对于每个元素，每次不再只移动一位，而是“大踏步”的移动。（针对第一点）经过“大踏步”的移动以后，顺序相对好很多，此时再进行插入排序，效果会好很多。
针对上面你的想法，我们再具体的提出一些改进。
比如，对于一个有9个元素的list，我们取gap为3，先对index为0,3,6的元素进行插入排序，再对1,4,7的子列表插入排序，再对2,5,8的子列表进行插入排序。
经过对这三个子列表进行排序以后，我们发现此时的列表相对好了很多：
此时再进行插入排序，只需要再经过三次的替换就行了：
另外我们注意到，gap == 子列表数。比如，我们设定gap为3，那么子列表的数目也就是3。怎么理解呢，也很好理解：从第0位元素出发，3为gap向右走到头是sublist1，同理从第1位出发， 第2位出发，可以得到sublist2，sublist3。这三个子列表就已经把整个list给遍历完了。
也就是说，对于一个gap，我们会得到gap个子列表，而这gap个子列表的起始元素列表是
start_list = [x for i in range(gap)]
我们可以通过上面的理解，得到要进行插入排序的每个子列表的起始元素。
我们再定义一个插入排序函数，就是上一节的插入排序代码，只不过gap不再是1了。传入列表nums，子列表的起始元素start，gap，我们便可以对这个子列表进行插入排序。
而这里的希尔排序，我们不是固定了gap，我们先采用最大的gap（即len(nums)//2），然后依次将gap除以2，直到gap为1进行最后的插入排序。比如上面例子中，我们采用的是长度为9 的list，那么我们先用gap为4，此时就有四个子列表，我们对这四个子列表调用插入排序的函数。下次gap为2，就有2个子列表，再调用插入排序的函数。。。
代码思路
- 所以需要一个while循环，循环对不同的gap进行分列表以及排序操作，循环结束条件为gap等于0.
- while里再需要一个for循环，按照上面所说对gap子列表调用插入排序函数。
- 定义一个传入start，gap，nums，能进行插入排序的函数。
代码实现：
def shellSort(nums):
#gap初始化为最大的gap，然后在while循环中不断整除2，减小gap
gap = len(nums)//2
while gap > 0:
#对gap个子列表调用插入排序函数
for startposition in range(gap):
gapInsertionSort(nums,startposition,gap)
print("After increments of size",gap,
"The list is",nums)
gap = gap // 2
#输入nums，起始位置，gap，就可以选出子列表，并且进行插入排序
def gapInsertionSort(nums,start,gap):
for i in range(start,len(nums),gap):
cur = i
while cur >= gap:
if nums[cur - gap] > nums[cur]:
temp = nums[cur - gap]
nums[cur - gap] = nums[cur]
nums[cur] = temp
cur -= gap
else:
break
nums = [54,26,93,17,77,31,44,55,20]
shellSort(nums)
print(nums)
