〇、算法概述
0.0算法分类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较累排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.1算法复杂度
（1）名词解释
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
一、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
1.0算法描述
（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
（3）针对所有的元素重复以上的步骤，除了最后一个；
（4）重复步骤1~3，直到排序完成。
1.1动图演示
1.2代码实现
public static int[] bubbleSort(int[] sortArray) {
//数组元素个数n
int n = sortArray.length;
//外循环执行n-1次，每循环一次数组无序段中最大的数就会被轮换到末尾，成为有序段的起始元素。
for (int i = 0; i < n-1; i++) {
//内循环执行n-1-i次,排除有序段的重复比较。
for (int j = 0; j < n-1-i; j++) {
if (sortArray[j] > sortArray[j + 1]) {
int temp = sortArray[j];
sortArray[j] = sortArray[j + 1];
sortArray[j + 1] = temp;
}
}
}
return sortArray;
}
二、选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.0算法描述
（1）初始状态：无序区为R[1..n]，有序区为空；
（2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
（3）n-1趟结束，数组有序化了。
2.1动图演示
2.3代码实现
public static int[] selectSort(int[] sortArray){
//数组元素个数n
int n = sortArray.length;
//最小元素下标（默认为0）
int miniIndex = 0;
int temp;
//外循环执行n-1次，从第一个元素开始比较
for (int i = 0; i < n-1; i++) {
//内循环从i+1下标元素开始
for (int j = i+1; j < n; j++) {
if ( sortArray[j] < sortArray[miniIndex]){
miniIndex = j;
}
}
temp = sortArray[i];
sortArray[i] = sortArray[miniIndex];
sortArray[miniIndex] = temp;
}
return sortArray;
}
2.3 算法分析
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。
三、插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3.0算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
（1）从第一个元素开始，该元素可以认为已经被排序；
（2）取出下一个元素，在已经排序的元素序列中从后向前遍历扫描；
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
（5）将新元素插入到该位置后；
（6）重复步骤2~5。
3.1动图演示
3.2代码实现
public static int[] insertionSort(int[] sortArray){
//数组元素个数n
int n = sortArray.length;
//当前待插入元素的前一个元素索引
int preIndex;
//当前待插入元素
int current;
//从第二个元素开始，默认第一元素为归为有序段
for (int i = 1; i < n ; i++) {
current = sortArray[i];
preIndex = i-1;
while (preIndex >= 0 && sortArray[preIndex] > current){
sortArray[preIndex+1] = sortArray[preIndex]; //如果前元素比当前待插入元素大则向后移动一个位置
preIndex--;
}
sortArray[preIndex+1] = current; //插入元素
}
return sortArray;
}
3.3算法分析
插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
四、希尔排序（Shell Sort）
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
4.0算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
（1）选择一个增量序列t1，t2，ti，tj…，tk，其中ti>tj，tk=1；（如4，2，1）
（2）按增量序列个数k，对序列进行k 趟排序；
（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.1动图演示
4.2代码实现
public static int[] shellSort(int[] sortArray){
//数组元素个数n
int n = sortArray.length;
//当前增量为gap,以增量划分序列
for (int gap = (int) Math.floor(n/2); gap > 0 ; gap = (int) Math.floor(gap/2)) {
//对子序列[gap-n]进行插入排序,[0-gap]段默认为有序段
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
for (int i = gap; i < n; i++) {
//当前待插入元素索引
int currentIndex = i;
//当前待插入元素
int current = sortArray[i];
while (currentIndex-gap >= 0 && current < sortArray[currentIndex-gap]){
sortArray[currentIndex] = sortArray[currentIndex-gap];
currentIndex = currentIndex-gap;
}
sortArray[currentIndex] = current;
}
}
return sortArray;
}
4.3算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
五、归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
5.0算法描述
（1）把长度为n的输入序列分成两个长度为n/2的子序列；
（2）对这两个子序列分别采用归并排序；
（3）将两个排序好的子序列合并成一个最终的排序序列。
5.1动图描述
5.2代码实现
function mergeSort(arr) {
varlen = arr.length;
if(len < 2) {
returnarr;
}
varmiddle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
returnmerge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
varresult = [];
while(left.length>0 && right.length>0) {
if(left[0] <= right[0]) {
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length)
result.push(left.shift());
while(right.length)
result.push(right.shift());
returnresult;
}
5.3代码分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
六、快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6.0算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
（1）从数列中挑出一个元素，称为 “基准”（pivot）；
（2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.1动图演示
6.2代码实现
/**
*
* @param sortArray 排序数组
* @param startIndex 排序段起始索引
* @param endIndex 排序段结束索引
*/
public static void quickSort(int[] sortArray, int startIndex, int endIndex){
if (startIndex >= endIndex) {
return;
}
int leftIndex = startIndex;
int rightIndex = endIndex;
//取基准值（基准元素），默认为起始索引元素
int temp = sortArray[leftIndex];
//若左索引小于右索引，则继续执行
while (leftIndex < rightIndex) {
//若左索引小于右索引，且右索引元素大于等于基准值，则不做元素移动，右索引左移
while (leftIndex < rightIndex && temp <= sortArray[rightIndex]) {
rightIndex--;
}
//判断右索引为何不再左移，若右索引指向元素小于基准值，则把该元素赋值于左索引指向元素，同时左索引向右移动
if (leftIndex < rightIndex) {
sortArray[leftIndex] = sortArray[rightIndex];
leftIndex++;
}
//若左索引小于右索引，且左索引元素小于等于基准值，则不做元素移动，左索引右移
while (leftIndex < rightIndex && sortArray[leftIndex] <= temp) {
leftIndex++;
}
//判断左索引为何不再右移，若右索引指向元素小于基准值，则把该元素赋值于左索引指向元素，同时左索引向右移动
if (leftIndex < rightIndex){
sortArray[rightIndex] = sortArray[leftIndex];
rightIndex--;
}
}
//当左索引不在小于右索引时（此时左、右索引应该相等），把基准值（基准元素）放在左（右）索引位置
//此时基准元素左边的元素都比基准元素小，基准元素右边的元素都比基准元素大
sortArray[leftIndex] = temp;
//分别对基准值左右两段数组进行递归调用，做同样的元素移动操作
quickSort(sortArray,startIndex,leftIndex-1);
quickSort(sortArray,rightIndex+1,endIndex);
}
七、快速排序（Quick Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
7.0 算法描述
（1）找出待排序的数组中最大和最小的元素；
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
7.1动图演示
7.2代码实现
public static int[] CountingSort(int[] sortArray,int maxValue){
//创建一个容量为最大数的数组
int[] temp = new int[maxValue];
//对需排序数组中元素出现的个数对应记录到temp数组的对应下标
for (int i = 0; i < sortArray.length ; i++) {
temp[sortArray[i]]++;
}
int index = 0;
for (int i = 0; i < temp.length; i++) {
while (temp[i] > 0){
sortArray[index++] = i;
temp[i]--;
}
}
return sortArray;
}
}
7.3算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，局限性较大，计数排序是一个很有效的排序算法。
