在这篇文档中将介绍几种排序法，冒泡排序和简单选择排序已经在前面博客中提过，在此不再赘述。

排序算法分类：



以下是几种排序法的比较：



稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

八种排序法对比：

序列长度较短时       序列长度较长时

选择排序法              快速排序法

插入排序法              堆排序法

冒泡排序法              归并排序法

1.堆排序法（Heapsort）堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

2.归并排序是将一组无序数列分组比较再排序的方法。

                                                        

然后将两组排好序的数列合并排序。



最后结果如下：



 

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

3.插入排序法

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。



一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
	
取出下一个元素，在已经排序的元素序列中从后向前扫描；
	
如果该元素（已排序）大于新元素，将该元素移到下一位置；
	
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
	
将新元素插入到该位置后；
	
重复步骤2~5。
function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

4.希尔排序：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。



 



 

 

 

 

这篇文章是对于 JS 中 数组排序 的常见方法的一个总结 ：

前置知识 ：


排序大的分类可以分为两种：内排序 和  外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。



内排序有可以分为以下几类：

插入排序：直接插入排序、二分法插入排序、希尔排序。
	
选择排序：直接选择排序、堆排序。
	
交换排序：冒泡排序、快速排序。
	
归并排序
	
基数排序



稳定性

稳定：归并排序、冒泡排序、插入排序，基数排序。
	
不稳定：选择排序、快速排序、希尔排序、堆排序。



时间复杂度

最基础的四个算法：冒泡、选择、插入、快排 中，快排的 时间复杂度 最小 O(n*log2n)，其他都是O（n2）。


排序在 JS 中 :（基础的四个算法：冒泡、选择、插入、快排）

sort 方法 （a-b正向    b-a 反向）

内部原理：冒泡排序。

JavaScript中数组的 sort() 方法主要用于对数组的元素进行排序。其中，sort()方法有一个可选参数。但是，此参数必须是函数。 数组在调用 sort()方法时，如果没有传参将按字母顺序（字符编码顺序）对数组中的元素进行排序，如果想按照其他标准进行排序，就需要进行传一个参数且为函数，该函数要比较两个值，并且会返回一个用于说明这两个值的相对顺序的数字。


let arr=[3,1,5,8,28]
//正向 a-b
var arr1=arr.sort(function  (a,b) {
return a-b;
})
console.log(arr1) //[1,3,5,8,28];

//反向 b-a
var arr2=arr.sort(function  (a,b) {
return b-a;
})
console.log(arr2) //[28,8,5,3,1]


冒泡排序 

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。


function sortArr(arr){
    for(let i=0; i<arr.length; i++){
        //arr.length-i 保证每次比较都会少比较一位（因为最大的一位已经找出，放在了最后）
        for(let j=0; j<arr.length-i; j++){
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

快速排序 （一拆为二）

首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面,然后对左右部分递归。


function quickSort(arr){
    //如果数组长度小于等于1，则返回数组本身
    if(arr.length<=1){
        return arr;
    }
    //定义中间值的索引
    var index = Math.floor(arr.length/2);
    //取到中间值
    var center = arr.splice(index,1);
    //定义左右部分数组
    var left = [];
    var right = [];
    for(var i=0;i<arr.length;i++){
    //如果元素比中间值小，那么放在左边，否则放右边
        if(arr[i]<center){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(center,quickSort(right));
}


选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。


function selectSort(arr){
    for(var i=0;i<arr.length;i++){
        //设置当前范围最小值和索引
        var min = arr[i];
        var minIndex = i;
        //在该范围选出最小值
        for(var j=i+1;j<arr.length;j++){
            if(min>arr[j]){
                min = arr[j];
                minIndex = j;
            }
        }
        //将最小值插入
        arr.splice(i,0,min);
        //将原来位置的最小值删除
        arr.splice(minIndex+1,1);
    }
}

插入排序 

假设第 0 元素是有序序列，第 1 元素之后是无序的序列。从第 1 元素开始依次将无序序列的元素插入到有序序列中。


function insertSort(arr){
//假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中
    for(var i=1; i<arr.length;i++){
        if(arr[i]<arr[i-1]){
            //取出无序序列中需要插入的第i个元素
            var temp = arr[i];
            //定义有序中的最后一个位置
            var j = i-1;
            arr[i] = arr[j];
            //比较大小，找到插入的位置
            while(j>=0&&temp<arr[j]){
                arr[j+1] = arr[j];
                j--;
            };
            //插入
            arr[j+1] = temp;
        }
    }
  }


这里只是简单的总结了下自己常用的几种，如果想了解更多，请参考下方链接：

https://blog.csdn.net/weixin_41725746/article/details/93080926



 

堆排序的基本原理：
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

大顶堆举例说明：



我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子:


堆排序的算法分析：
①、将待排序序列构造成一个大顶堆

②、此时，整个序列的最大值就是堆顶的根节点。

③、将其与末尾元素进行交换，此时末尾就为最大值。

④、然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

（可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了）
堆排序算法图解：
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下



2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。



4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。



这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。



此时，我们就将一个无需序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换



b.重新调整结构，使其继续满足堆定义



c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.



后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序



再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

图片转载自
详细代码：
package Tree;

import java.util.Arrays;

/**
 * @ClassName: HeapSort
 * @Description: 对数组进行升序排序
 * @author Golven
 * @date 2019年10月27日
 *
 */
public class HeapSort {

	public static void main(String[] args) {
		int[] arr = { 4, 6, 8, 5, 9 };
		heapSort(arr);
	}

	public static void heapSort(int[] arr) {
		int temp =0;
		System.out.println("堆排序：");
		for(int i = arr.length/2-1;i>=0;i--) {
			adjustHeap(arr, i, arr.length);
		}
		for(int j = arr.length-1;j>0;j--) {
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			//再从0开始调整，相当于将余下的数再次进行堆排序，顶上元素最大
			adjustHeap(arr, 0, j);
		}
		
		System.out.println(Arrays.toString(arr));
	}

	/**
	 * 
	 * @Title: adjustHeap
	 * @Description: 完成将以i对应的节点的非叶子节点的树调整为大顶堆
	 * @param @param i 表示非叶子节点在数组中的索引
	 * @param @param arr 待调整的数组
	 * @param @param length 对多少个元素进行调整，length时逐渐减小的
	 * @return void 返回类型 
	  * 举例：int arr[]={ 4, 6, 8, 5, 9}==>i=1==>adjustHeap==>{4,9,8,5,6}==> 再次调用adjustHeap==>i=0==>{9,6,8,5,4}         
	 */
	public static void adjustHeap(int[] arr,int i,int length) {
		//定义辅助变量将arr[i]的值赋给它
		int temp =arr[i];
		//k=2*i+1表示从i的左节点开始调整
		for(int k = 2*i+1;k<length;k=2*k+1) {
			if(k+1<length&&arr[k]<arr[k+1]) {//左节点的值小于右节点的值
				k++;//将k指向右节点
			}
			if(arr[k]>temp)//右节点的值大与父节点
			{
				arr[i]=arr[k];
				i=k;
			}
			else {
				break;
			}
			arr[i] =temp;
		}
	}
}

一 选择排序：

  选择排序的工作原理是从 待排序的元素中选出最小或者最大的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。这是一种不稳定的排序方法。比冒泡排序快。

二 冒泡排序：

  冒泡排序重复访问要排序的元素，依次比较两个相邻的元素。如果前一个元素大于后一个，或者小于，就把它们交换过来。重复的进行直到没有相邻元素需要交换，说明冒泡排序已经完成。时间复杂度为o(n2)。

以下是代码实现(c++)：

#include <iostream>

using namespace std;

//选择排序
void selectSort(int (&a)[10])
{
	for (int i = 0; i < 10; i++)
	{
		//从下一个数开始
		for (int j = i + 1; j < 10; j++)
		{
			//交换
			if (a[i]>a[j])
			{
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}

}

//冒泡排序
void bubbleSort(int(&a)[10])
{
	for (int i = 0; i < 10;i++)
	{
		for (int j = 0; j < 10 - i - 1;j++)
		{
			//交换
			if (a[j]>a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}

		}
	}

}

//主函数
int main()
{
	int array[10] = {10,8,6,19,3,41,4,7,98,1};
	cout << "排序前：";
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		cout << array[i] << " ";
	}

	//selectSort(array);
	bubbleSort(array);

	cout << "排序后：";
	for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		cout << array[i] << " ";
	}


	return 0;
}