常见的排序算法

发表于   |   分类于

参考网址：http://blog.csdn.net/matrix_laboratory/article/details/9304043

分类 基础排序O(n^2) 高级排序O(nlogn)
交换 冒泡排序 快速排序
插入 插入排序 希尔排序
选择 选择排序 [堆排序]
其它 － 归并排序

基础排序

1. 冒泡排序

原理：比较相邻两个数，如果前者小于后者，就把两个数交换位置；那么第一轮就可以选出一个最小的数放在最后面；经过 n-1 轮，就完成了所有数的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(array){
    var temp;
 	for(var i=0;i<array.length;i++){
	   	for(var j=array.length-1;j>i;j--){
	    	if(array[j]<array[j-1]){
	    		temp = array[j];
	    		array[j]=array[j-1];
	    		array[j-1]=temp;
	    	}
	    }
	}
	return array;
}

时间复杂度

比较次数 移动次数
最好 n(n-1)/2 = o(n^2) 0
最坏 n(n-1)/2 = o(n^2) n(n-1)/2 = o(n^2)
平均 n(n-1)/2 = o(n^2) n(n-1)/4 = o(n^2)

2. 插入排序

原理：从数组第二个值开始，依次将后续的数值与前面排序后的序列比较后插入。如下图：

quick sort.gif

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort(array) {  
    var key;
  	for(var i=1; i<array.length ; i++){ 
		var j=i-1;
		key = array[i];
		while(j>=0 &&	 array[j]>key){  
			array[j+1] = array[j];       
			j--;        
		}
		array[j+1] = key;
	}
	return	array;
}

时间复杂度

比较次数 移动次数
最好 n/2 = o(n) 0
最坏 n(n-1)/2 = o(n^2) n(n-1)/2 = o(n^2)
平均 o(n^2) n(n-1)/4 = o(n^2)

3. 选择排序

原理：把每一个数都与第一个数比较，记住最小的数的下标，用最小的数和第一个数交换位置，这样一轮下来，最小的数就排到了最前面。重复 n-1 轮，就实现了选择排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function selectSort(array){
  var minIndex,temp;
    
  for(i=0;i<array.length-1;i++){
    minIndex=i;
    
    for(j=i+1;j<array.length;j++){
      if(array[j]<array[minIndex]){
        minIndex=j;  // 将最小数的索引保存
      }
    }
    
    temp=array[i];
    array[i]=arr[minIndex];
    array[minIndex]=temp;
  }
  
  return array;
}
比较次数 移动次数
最好 n(n-1)/2 = o(n^2) 0
最坏 n(n-1)/2 = o(n^2) n-1
平均 n(n-1)/2 = o(n^2) n-1

高级排序

1. 快速排序

原理：在数据集之中，选择一个元素作为”基准”（pivot）。所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSort(arr) {
　　if (arr.length <= 1) { return arr; }

　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

2. 希尔排序

原理：根据增量分割数组，对每一个数组使用插入排序。再把增量变为减半后进行分割，直到增量为 1，再对全体进行一次直接插入排序就可以了.

举个例子：

1
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

增量为 5，则分割为：

1
2
3
4
5
[3,15,46]
[44,36,4]
[38,26,19]
[5,27,50]
[47,2,48]

对每一组进行直接插入排序。再把增量变为 2(减半)，再进行分割，直到增量为 1，再对全体进行一次直接插入排序就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var len =arr.length;
    gap = Math.floor(len/2);
    while(gap!==0){
        for(var i = gap;i<len;i++){
            var temp = arr[i];
            var j;
            for(j=i-gap;j>=0&&temp<arr[j];j-=gap){
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
        gap=Math.floor(gap/2);
    }
  return arr;
比较次数 移动次数
最好 n*log2 n 0
最坏 n*log2 n n-1
平均 n*log n n-1

3. 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
var len;    

// 建立大顶堆
function buildMaxHeap(arr) {   
    len = arr.length;
    for (var i = Math.floor(len/2); i &gt;= 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;
}

其它

归并排序

参考网址：http://blog.csdn.net/fendou_dexiaoniao/article/details/46594125

分治策略，先进行划分，然后再进行合并。

假设要对数组 C 进行归并排序，步骤是：
1.先将 C 划分为两个数组 A 和 B（即把数组 C 从中间分开）
2.再分别对数组 A、B 重复步骤 1 的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。

如：[12 20 30 21 15 33 26 19 40 25]

划分为: 

1
2
3
4
       [12 20 30 21 15]            [33 26 19 40 25]  
   [12 20]      [30 21 15]       [33 26]       [19 40 25]  
 [12]  [20]   [30]  [21 15]     [33]  [26]    [19]    [40 25]
[12]  [20]   [30] [21] [15]    [33]  [26]    [19]   [40] [25]

3.然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。

4.依次类推，直到合并到最上层结束，这时数据的排序已经完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function mergeSort(arr){  
  if(arr.length==1) {return arr};  
  var mid=Math.floor(arr.length/2);  
  var left_arr=arr.slice(0,mid), right_arr=arr.slice(mid);  
  return merge(mergeSort(left_arr), mergeSort(right_arr));  
} 

function merge(left, right) {  
  var result = [];  
  while(left.length > 0 && right.length > 0) {  
     if(left[0] < right[0]) {  
       result.push(left.shift());  
     }  
     else {  
       result.push(right.shift());  
     }  
   }  
  
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */  
   return result.concat(left).concat(right);  
}
比较次数
最好 n*log2 n
最坏 n*log2 n
平均 n*log2 n

归并的时间复杂度分析：主要是考虑两个函数的时间花销，

一、数组划分函数 mergeSort()；
二、有序数组归并函数 merge()；

mergeSort() 函数的时间复杂度为 O(n)，因为代码中有 2 个长度为 n 的循环（非嵌套），所以时间复杂度则为 O(n)；

简单的分析下元素长度为 n 的归并排序所消耗的时间 T[n]：调用 mergeSort() 函数划分两部分，那每一小部分排序好所花时间则为 T[n/2]，而最后把这两部分有序的数组合并成一个有序的数组 mergeSort() 函数所花的时间为 O(n)；