在看<<大话数据结构>>这本书中关于排序这一章的时候，我试着用javascript语言来重写里面几个经典的排序方法，包括冒泡排序、快速排序、选择排序、插入排序还有希尔排序。
一、冒泡排序
冒泡排序算是排序中最常见的，冒泡排序分为两个，一种是从小到大，一种是从打到小，具体是实现步骤就是：从最开始的位置或者最后的位置反方向对比，如果比它大/小，就交换然后继续走，第一遍走完，最后一个位置是最大值或者最小值，时间复杂度为O（n^2），是稳定的排序，用JS实现的代码如下：
//冒泡排序
function exchange(array,i,j){
var t = array[i];
array[i] = array[j];
array[j] = t;
}
function bubbleSort(arr){
for(var i=0; i<arr.length; i++){
for(var j=0;j<arr.length-i;j++){
if(arr[j] > arr[j+1]){
exchange(arr,j,j+1);
}
}
console.log(arr.toString());
}
return arr;
}
var nums = [2,3,4,3,1,5,7,122,341,-1];
console.log(bubbleSort(nums));
在浏览器上显示的步骤为：
冒泡.PNG
二、快速排序
快速排序就是一开始找一中点，然后把比它小的放左边，比它大的放右边，然后重新对中介两边的数组，各自重新执行快速排序，如此循环，代码如下：
//快速排序
function quickSort(arr){
if(arr.length <= 1){
return arr;
}
console.log("原数组是:" + arr);
var pivotIndex = Math.floor(arr.length/2);
var pivot = arr.splice(pivotIndex,1)[0];
console.log("将中介提取出来后数组是:"+arr);
var left = [];
var right = [];
for(var i=0;i<arr.length;i++){
console.log("此刻中介是:"+pivot+"当前元素是:"+arr[i]);
if(arr[i] > pivot){
right.push(arr[i]);
console.log("移动元素:"+arr[i]+"到右边");
} else{
left.push(arr[i]);
console.log("移动元素:"+arr[i]+"到左边");
}
}
return quickSort(left).concat([pivot],quickSort(right));
}
console.log(quickSort(nums));
快速排序的时间复杂度为O(nlogn),属于不稳定排序。
三、选择排序
选择排序就是选择数组中第一个元素，将它和其他元素进行对比，跟最小的交换，然后从第二个元素开始，继续跟后面的比，跟剩余里面最小的交换，直到循环结束，代码如下：
//选择排序
function selectSort(arr){
var min = 0;
for(var i=0;i<arr.length;i++){
min = i;
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[min]){
min = j;
}
}
if(i!=min){
exchange(arr,i,min);
}
}
return arr;
}
console.log(selectSort(nums));
选择排序的时间复杂度为O(n^2)。
四、插入排序
插入排序就是将数组分成“已排序”和“未排序”两部分，刚开始，“已排序”的部分只有一个元素，就是第一个元素，然后依次将后面”未排序“中的元素，部分插入到“已排序”中，从而“已排序”部分增加一个元素，“未排序”部分减少一个元素，直到循环结束，代码如下：
//直接插入排序
function insertSort(arr){
console.log("原数组:"+arr);
for(var i=0;i<=arr.length;i++){
for(var j=i;j>0 && arr[j]<arr[j-1];j--){
exchange(arr,j,j-1);
console.log("此时数组:"+arr);
}
}
return arr;
}
console.log(insertSort(nums));
插入排序的时间复杂度为O(n^2),是稳定的排序。
五、希尔排序
希尔排序的实质是分组插入排序，该方法又称缩小增量排序。该方法的基本思想是：先将整个待排元素序列分割为若干个子序列（由相隔某个‘增量’的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，带这个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况）效率是很高的，因此希尔排序在时间效率上有较大的提高，代码如下：
//希尔排序
function shellSort(arr){
console.log("原数组:"+arr);
var increment = arr.length;
var i = 0;
var temp = 0;
do{
increment = Math.floor(increment / 3) + 1;
for(i = increment; i < arr.length; i++){
if(arr[i] < arr[i-increment]){
temp = arr[i];
for(var j = i-increment; j>=0 && temp < arr[j]; j-=increment){
arr[j + increment] = arr[j];
}
arr[j + increment] = temp;
}
}
}while(increment > 1);
return arr;
}
console.log(shellSort(nums));
网友评论