排序的基本概念

1.排序：排序是按关键字的非递减或非递增顺序对一组记录重新进行排序的操作

2.排序的稳定性：对于关键字相同的元素，如果排序前后的相对位置没有改变就认为该排序算法是稳定的

3.内部排序和外部排序：由于待排序记录的数量不同，使得排序过程中数据所占用的存储设备会有所不同，可分为两大类：一类是内部排序，指的是待排序记录全部存储在计算机内存中进行排序的过程；另一类是外部排序，指的是待排序记录的数量很大，以至内存一次不能容纳全部的记录，再排序的过程中尚需对外存进行访问的排序过程

内部排序算法的分类

就分类全面性能而言，很难提出一种被认为是最好的方法，每一种方法都各有优缺点，适用在不同的环境(如记录的初始排列状态)下使用

内部排序的过程是一个逐步增大记录有序序列长度的过程。在排序的过程中，可以将排序记录区分为两个区域：有序序列区和无序序列区

使有序区中记录的数目增加一个或几个的操作称为一趟排序

根据逐步扩大记录有序序列长度的原则不同，可以将内部排序分为以下几类：

1. 插入类：将无序序列的一个或几个记录“插入”到有序序列中，从而增加记录的有序序列长度。主要包括直接插入排序、折半插入排序和希尔排序
2. 交换类：通过交换无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序序列中，以此方法增加记录的有序序列的长度。主要包括冒泡排序和快速排序
3. 选择类：从记录的无序子序列中选择关键字最大或最小的记录，并将它加入到有序子序列中，以此方法增加有序序列的长度。主要包括简单选择排序、树形选择排序、堆排序
4. 归并类：通过归并两个或以上的记录有序子序列，逐步增加记录有序序列的长度。2-路归并排序是最为常见的归并排序方法
5. 分配类：是唯一一类不需要进行关键字之间比较的排序方法，排序时主要利用分配和收集两种基本操作来完成。基数排序是主要的分配类排序方法。

待排序记录的存储方式

1. 顺序表：记录之间的次序关系由其存储位置决定，实现排序需要移动记录
2. 链表：记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针即可。这种排序方式称为链表排序
3. 待排序记录记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束之后再按照地址向量中的值调整记录的存储位置。这种排序方式称为地址排序。

算法实现借助于python3，相关代码以上传至https://github.com/bingnan125/sort/blob/master/sort.py

插入排序

直接插入排序

  直接插入排序是一种简单插入排序，基本思想是：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程

  类似我们摸牌，一开始有一堆牌（待排序的）。由于第一次摸牌时手中没牌，所以不需要排序。第二次摸牌时和手中第一张拍比较，如果它大，就放在它的后面。 每次摸牌都会把牌放在一个前面比自己小（或等于），后面比自己大（或等于）的位置。

希尔排序

  该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

选择排序

简单选择排序

  从待排序序列中，找到关键字最小的元素，如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换。从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

 

堆排序

  什么是堆？
  堆是一棵顺序存储的完全二叉树。
小根堆：每个结点的关键字都不大于其孩子结点的关键字。
大根堆：每个结点的关键字都不小于其孩子结点的关键字。
对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：
  (1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
  (2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
  利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
  其基本思想为(大顶堆)：
  1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
  构建初始堆

整体排序流程

交换排序

冒泡排序

  它适合数据规模很小的时候，而且它的效率也比较低，但是作为入门的排序算法，还是值得学习的。
  什么是冒泡排序？
  顾名思义，像水里吐的泡泡一样，因为水越深压强越大，而泡泡的在水里的由深变浅。所以，同样的气体体积，第一个出来的泡泡比第二个出来的要大。

快速排序

  设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
  排序流程
  1.首先哨兵j从右开始找比基位6小的数，注意这里一定是哨兵j先开始走，因为和基位交换的是哨兵i。如果哨兵j一直没有找到比基位6小的数就会和哨兵i相遇。说明哨兵i所在的位置基位（因为哨兵i还没开始走）是最小值基位6。直到哨兵j找到比基位小的数，哨兵i才开始从左开始找比基位6大的数。

  2.哨兵j从右开始找比基位6小的数“5”，哨兵i比基位6大的数“7”

  3.交换“5”跟“7”的位置

  4.继续重复1-3的步骤


  5.哨兵j继续往左走，找到了比基位6小的数“3”后停止。然后哨兵i往右走找比基位6大的数。正好哨兵i和哨兵j相遇，所有的数都已经和6比较完了。这时候哨兵i的位置和基位“6”交换。


  6.交换完后“6”左边的都比“6”小，“6”右边的都比“6”大

  7.继续按上面的步骤比较“6”左边的3，1，2，5，4和右边的9，7，10，8直到所有的数都为有序状态

归并排序

  归（递归）并（合并）排序采用了分治策略（divide-and-conquer），就是将原问题分解为一些规模较小的相似子问题，然后递归解决这些子问题，最后合并其结果作为原问题的解。
  归并排序将待排序数组A[1..n]分成两个各含n/2个元素的子序列，然后对这个两个子序列进行递归排序，最后将这两个已排序的子序列进行合并，即得到最终排好序的序列。具体排序过程如下图所示：

基数排序

  基数排序(radix sort)又称桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。它是一种稳定的排序算法，但有一定的局限性：
　　1、关键字可分解；
　　2、记录的关键字位数较少，如果密集更好；
　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
  初始化：构造一个10*n的二维数组，一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。
  循环操作：从低位开始（我们采用LSD的方式），将所有元素对应该位的数字存到相应的桶子里去（对应二维数组的那一列）。然后将所有桶子里的元素按照桶子标号从小到大取出，对于同一个桶子里的元素，先放进去的先取出，后放进去的后取出（保证排序稳定性）。这样原数组就按该位排序完毕了，继续下一位操作，直到最高位排序完成。
  待排序的数组：70, 34, 65, 24, 48, 32, 88, 16, 38, 81
  按个位排序：

个位	0	1	2	3	4	5	6	7	8	9
	70	81	32		34	65	16		48
					24				88
									38

  按个位排完之后的顺序：70，81，32，34，24，65，16，48，88，38
  按十位排序：

十位	0	1	2	3	4	5	6	7	8	9
		16	24	32	48		65	70	81
				34					88
				38

  按十位排完之后的顺序：16，25，32，34，38，48，65，70，81，88

时间复杂度

  复杂度函数时间大小比较

参考：https://blog.****.net/lyhkmm/article/details/78920769

          数据结构(C语言版)