排序算法的基本概念
什么叫排序？
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
排序算法的性质
稳定性
稳定的算法，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
反之，不稳定的算法，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中S在R之前。
时间复杂度（最差、平均、和最好性能）T(n)
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。
T(n) = O(f(n))
一般而言，好的性能是 O(nlogn)，且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。
查看时间复杂度计算方式
空间复杂度S(n)
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
排序方式
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
更多详情
先来张总结性图片
冒泡排序（Bubble Sort）
定义
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（尾部），故名。
实现步骤
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个（因为每次最后遍历的最后一个数都是最大的，所以不需要再次比较了）。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
或许你还是不太了解，这里有该算法的详细实现过程
选择排序（Selection Sort）
定义
选择排序法是对定位比较交换法（也就是冒泡排序法）的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
实现步骤
1.第1趟，在待排序记录r[0]~r[n-1]中选出最小的记录，将它与r[0]交换，
2.第2趟，在待排序记录r[1]~r[n-1]中选出最小的记录，将它与r[1]交换，
3.以此类推…
4.第i趟，在待排序记录r[i-1]~r[n-1]中选出最小的记录，将它与r[i-1]交换，
5.使有序序列不断增长直到全部排序完毕。
PS：冒泡排序是逐次把当前序列中最大值推到后面去。
选择排序是逐次把当前序列中最小值放到前面去。
或许你还是不太了解，这里有该算法的详细实现过程
插入排序（Insertion Sort）
定义
每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。
直接插入排序实现步骤
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
或许你还是不太了解，这里有该算法的详细实现过程
二分法排序
定义
二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
实现步骤
1.二分法查找插入位置
如果R<R[m]成立，那右指针就要向左移动中间指针一位，否则，左指针要向右移动中间指针一位。反复查找，直到左指针大于右指针时停止。
2.后移，有点迷惑，什么时候需要后移呢？有哪些记录需要移动呢？
虽然我们很清楚的知道，我们需要后移那些排序码大于R的记录，但难免会问自己这样几个问题。其实它相当于需要移动从i-1到左指针的记录。
3.插入
由1中得到的左指针其实就是元素要插入的位置。
或许你还是不太了解，这里有该算法的详细实现过程
希尔排序（Shell Sort）
定义
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
实现步骤
对数组arr，长度为n进行排序
1.第一个增量为Math.floor(n/2)，再最每个小的分租进行直接插入排序；
2.第二个增量为Math.floor(n/4)，再最每个小的分租进行直接插入排序；
3.以此类推…，直到增量为1，这是排序完成。
或许你还是不太了解，这里有该算法的详细实现过程
归并排序（Merge Sort）
定义
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
实现步骤
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾,这时完成排序。
或许你还是不太了解，这里有该算法的详细实现过程
快速排序（Quicksort）
定义
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现步骤
一趟快速排序的算法是：排序序列A，N为排序序列长度
1.找基准（一般是以当前数组的第一项的值）
2.遍历数组，小于基准的放在left，大于基准的放在right
3.递归（再分别对数组 left 和 right 1,2步骤，直到不能再分组为止）
或许你还是不太了解，这里有该算法的详细实现过程
堆排序(Heapsort)
定义
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
实现步骤
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，则整个排序过程完成。
或许你还是不太了解，这里有该算法的详细实现过程
计数排序
定义
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。
实现步骤
1.找出待排序的数组中最大和最小的元素；
2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4.反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。
或许你还是不太了解，这里有该算法的详细实现过程
桶排序 (Bucket SORT）
定义
输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
实现步骤
1.找出排序数组 arr 中最小值min和最大值max，并设定用来排序的桶的数量 N。
2.计算出每个桶中的数据范围为 L = (max - min)/N。
3.再计算出 N 个桶的数值范围，如第一个桶[min, min + L),第二个桶[min + L, min + 2L),依次类推…
4.将数组arr分配到相应的桶中，再在每个桶的数据进行排序（一般插入排序就可）。
5.将桶中的数据依次取出放入新数组，这时新数组就是排好序的数组了。
或许你还是不太了解，这里有该算法的详细实现过程
基数排序（Radix Sort）
定义
基数排序属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
实现步骤
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。
以下红色字体代表桶编号
得到：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
再将这些桶子中的数值重新串接起来，成为以下的数列。
81, 22, 73, 93, 43, 14, 55, 65, 28, 39接着再进行一次分配，这次是根据十位数来分配
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
或许你还是不太了解，这里有该算法的详细实现过程
总结
这些算法我还记得在大学时学过的，只不过当然并没有太在意，这也许就是–欠下的债，终究是要还的。
