排序算法的设计与实现
这是一个可视化的排序展示,支持冒泡、插入和选择排序，具体使用先 随机添加40个，然后点排序，就可以看到可视化的效果。
推荐一下，HTML5 Canvas Demo:Sorting Algorithms,这里还有个可视化的排序博客，各大排序算法的实现都栩栩如生。
JavaScript写排序算法主要是参数问题，比如JavaScript算法函数可以扔给Array原型：Array.prototype.sort = function，也可以直接写个函数带参数：function sort(array) {}，哪种方法都一样，需要注意的是兼容性问题，如果可以考虑所有可遍历对象都能排序（比如argument），才大法好！
下面的排序都是从小到大的排序：
插入排序
插入排序是一种基本排序，它的基本思路是构建有序序列，对于未排序的数据，在已排序的基础上，从右向左（或者二分查找）选择位置插入。
1
2
3
4
5
6
7
8
9
10
11
| function insert_sort(input) {
var i, j, temp;
for(i = 0; i < input.length; i++){
temp = input[i];
for(j = i-1; j >= 0 && input[j] > temp; j--) {
input[j+1] = input[j];
}
input[j+1] = temp;
}
return input;
}
|
如果以比较次数和移动次数来衡量算法的效率，最好的情况下，比较n-1次，移动0次，最坏情况，比较n(n-1)/2次，移动n(n-1)/2次。
二分插入排序
思路基本与插入算法相同，只是在查找插入位置的时候，不是依次查找，而是采用二分法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| function bin_insert_sort(input) {
var i, j, low, mid, high, temp;
for(i = 0; i < input.length; i++) {
temp = input[i];
high = i - 1;
low = 0;
while(low <= high) {
min = parseInt((low + high)/2);
if(temp < input[mid]) {
high = mid - 1;
}else {
low = mid + 1;
}
}
for(j = i - 1; j >= low; j--) {
input[j+1] = input[j]
}
input[low] = temp;
}
return input;
}
|
希尔排序
希尔排序其实是加强版的插入排序，就是在原先的插入排序的基础上，加入了步长，原先插入排序的步长是1，而且步长不同，效率也有差异，选择一个合适的步长也很重要。而且，希尔排序的最后一步，也必定是步长为1的插入排序，只不过此时整个排序已经基本稳定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function shell_sort(input) {
var gap, i, j, temp;
gap = input.length >> 1;
while(gap > 0) {
for(i = gap; i < input.length; i++) {
temp = input[i];
for(j = i - gap;j >= 0 && input[j] > temp; j -= gap) {
input[j + gap] = input[j];
}
input[j + gap] = temp;
}
gap = gap >> 1;
}
return input;
}
|
选择排序
选择排序的工作原理：首先在未排序序列中找到最小（大）元素，存放在排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function select_sort(input) {
var i, j, min, temp;
for(i = 0; i < input.length - 1; i++) {
min = i;
for(j = i + 1; j < input.length; j++) {
if(input[min] > input[j]) {
min = j;
}
}
temp = input[min];
input[min] = input[i];
input[i] = temp;
}
return input;
}
|
选择排序在最好的情况下和最坏的情况下，比较次数是一样的，都是n*(n-1)/2;
冒泡排序
冒泡排序的原理：对于待排序列，它会遍历多次，每次都会比较相邻的两个元素，若顺序相反，即交换他们。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function bubble_sort(input) {
var i, j, temp, flag;
for(i = 0; i < input.length - 1; i++) {
flag = true;
for(j = 0; j < input.length - i; j++) {
if (input[j] > input[j + 1]) {
temp = input[j];
input[j] = input[j + 1];
input[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
return input;
}
|
有flag时，最好的情况比较n-1次，移动0次，最坏情况，比较n(n-1)/2次，交换n(n-1)/2
快排
快排的基本思路就是选择一个元素，然后按照与这个元素的比较，将大于这个元素的都拿到右边，小于这个元素的都拿到左边，并找到这个元素的位置这个元素的左右两边递归。
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
| function quick_sort (input) {
function sort(start, end) {
if (start >= end) {
return;
}
var mid = partition(start, end);
sort(start, mid - 1);
sort(min + 1, end);
}
function partition(start, end) {
var left = start, right = end, key = input[start], temp;
while(left < right) {
while(left < right && input[right] >= key) {
right--;
}
input[left] = input[right];
while(left < right && input[left] <= key){
left++
}
input[right] = input[left];
}
input[left] = key;
return left;
}
sort(0, input.length - 1);
return input;
}
|
关于快排的详解