排序算法

排序基本概念

排序是计算机程序设计中的一种重要操作,他的功能是将一个数据元素(或记录)的任意排列,重新排列成一个按关键字有序的序列。
待排序的记录序列中可能存在两个或两个以上的关键字相等的记录,且在排序前Ri在Rj前面(即i
如果按照排序过程中依据的不同原则对内部排序进行分类,则可分为

  1. 插入排序
  2. 交换排序(快速排序)
  3. 选择排序
  4. 归并排序
  5. 基数排序

如果按照工作量来区分可以分为3类

  1. 简单的排序算法,时间复杂度为O(n2)
  2. 先进的排序算法,时间复杂度为O(nlogn)
  3. 基数排序,时间复杂度为O(d*n)

通常,在排序的过程中需要进行下列两种基本操作,(其中第二种操作可以通过改变记录的存储方式来予以避免)

  1. 比较两个关键字大小
  2. 将记录从一个位置移动至另一个位置
    待排序的记录序列可有下列3种存储方式。
  3. 存储在地址连续的一组存储单元上。
  4. 静态链表,记录之间的次序由指针指示,则实现排序不需要移动记录
  5. 待排序记录存储在一组地址连续的存储单元内,同时,另外设一个指示各个记录存储位置的地址向量,在排序过程中不移动记录本身,而是移动地址向量
    中这些记录的“地址”,在排序结束后再按照地址向量中的值调整记录的存储位置。

插入排序

直接插入排序 O(n2)

最为简单的一种排序,基本操作为将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录增1的有序表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//直接插入排序,更为高效的应该是折半插入排序¬≥
function insertSort (Arr) {
if (Arr.length <= 1) {
return Arr;
}
var temp;
for (var i = 1; i < Arr.length; i++) { //从1开始,第一个不用排序
temp = Arr[i]; //用temp缓存待插入的元素
for (var j = i; j >= 0; j--) {
if (temp < Arr[j]) {
Arr[j + 1] = Arr[j]; //当Arr[i]<Arr[j],则将Arr[j]往后移一位
} else if (temp > Arr[j]) {
break; //第一种:如果找到了一个比Arr[i]小的Arr[j],则退出循环,结束
}
//第二种,当j循环,结束
}
//结束j循环,将temp中缓存的待插入元素插入
Arr[j + 1] = temp;
}
}; //insert结束

其他插入排序

  1. 折半插入排序 O(n2) 通过减少比较关键字大小次数来优化排序算法。
  2. 2路插入排序
  3. 表插入排序

希尔排序 O(n3/2)

又被称为”缩小增量排序”。基本思想:先将整个待排记录序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录
“基本有序”时,再对全体记录进行一次直接插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function shellSort(Arr) {
var gap = Math.floor(Arr.length / 2);
while (gap > 0) {
for (var i = 0; i < Arr.length; i++) {
var temp = Arr[i];
for (var j = i; j >= gap && Arr[j - gap] > temp; j -= gap) {
Arr[j] = Arr[j - gap];
}
Arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return Arr;
}; //shell结束

快速排序

起泡排序 bubble sort

1
2
3
4
5
6
7
8
9
10
11
// 起泡排序,
function bibbleSort(Arr) {
for (var i = Arr.length - 1; i >= 0; i--) {
for (var j = 0; j < i; j++) {
if (Arr[j] > Arr[j + 1]) {
swap(j, j + 1, Arr);
}
}
}
return Arr;
};

快速排序 quick sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 一趟快速排序的算法是
// 1.设置初始值x=0,y=n-1,令keyValuey=Arr[0],2.从Arr[y]开始向前遍历,如果keyValue>Arr[y],则将Arr[i]和Arr[y]交换,3.从Arr[x]向后遍历,当keyValue<Arr[x]时;进行Arr[i]和Arr[y]交换,4.结束条件为x==y;
function quickSort (Arr) {
if (Arr.length <= 1) {
return Arr;
}
var pivotIndex = Math.floor(Arr.length / 2);
var pivot = Arr.splice(pivotIndex, 1);
var leftArr = [];
var rightArr = [];
for (var i = 0; i < Arr.length; i++) {
if (Arr[i] < pivot) {
leftArr.push(Arr[i]);
} else {
rightArr.push(Arr[i]);
}
}
return quickSort(leftArr).concat(pivot, quickSort(rightArr));
//quickSortOnce结束
}; //quick结束

选择排序

简单的选择排序

1
2
3
4
5
6
7
8
9
10
11
//选择排序 从待排序的数组中找出最小值放在最前面
function selectSort(Arr) {
for (var i = 0; i < Arr.length; i++) {
for (var j = i; j < Arr.length; j++) {
if (Arr[i] > Arr[j]) {
swap(Arr, i, j);
}
}
}
return Arr;
}; //select结束

树形选择排序

堆排序 heap sort

留!!!

归并排序 merging sort O(m+n)

假设初始序列含义n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,等到Math.floor(n/2)个长度为2或1的有序子序列,再两两归并,如此重复,直至得到一个长度为n的有序序列为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function mergeSort (){
var merge=function(left,right){
var final=[];
while(left.length&&right.length){
final.push(left[0]<=right[0]?left.shift():right.shift());
}
return final.concat(left.concat(right));
};
var len=this.length;
if(len<2){
return this;
}
var mid=parseInt(len/2),
_left=this.slice(0,mid),
_right=this.slice(mid);
return merge(_left.mergeSort(),_right.mergeSort());
};

基数排序 radix Sorting

各种排序算法比较

以上用到的swap函数

1
2
3
4
5
6
7
8
//swap函数
function swap(Arr, firPos, secPos) {
var temp = Arr[firPos];
Arr[firPos] = Arr[secPos];
Arr[secPos] = temp;
return Arr; //返回生成的数组
} //swap结束
分享 留言