冒泡排序（Bubble Sort）
已知一组无序数据a[0]、a[1]、……a[n]，需将其按升序排列。首先比较a[0]与a[1]的值，若a[0]大于a[1]则交换两者的值，否则不变。再比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]，依此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[0]a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[0]a[n-1]中最大的。再对a[0]~a[n-2]以相同方法处理一轮，依此类推。共处理n-1轮后a[0]、a[1]、……a[n]就以升序排列了。
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
/** 冒泡排序，升序
* @param {number[]} nums
* @return {number []}
*/
var bubbleSort = function(nums) {
var n = nums.length;
/*总循环次数 (n-1)+(n-2)+……+1 = n(n-1)/2 */
for (var i = n - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) { //升序：前者>后者 => 前者<后者,降序反之。
var temp = nums[j + 1];
nums[j + 1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
};
var res = bubbleSort([5, 4, 3, 2, 1]);
console.log(res);//[ 1, 2, 3, 4, 5 ]
【别人家的方法：实质相同】
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
选择排序（Selection Sort）
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
/** 选择排序，升序
* @param {number[]} nums
* @return {number []}
*/
var selectionSort = function(nums) {
var n = nums.length;
/*总循环次数 (n-1)+(n-2)+……+1 = n(n-1)/2 */
for (var i = 0; i < n - 1; i++) {
var minIndex = i;
for (var j = i + 1; j < n; j++) { //寻找最小的数
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
var temp = nums[minIndex];
nums[minIndex] = nums[i];
nums[i] = temp;
}
return nums;
};
var res = selectionSort([5, 4, 3, 2, 1]);
console.log(res);
插入排序（Insertion Sort）
将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
/** 插入排序，升序
* @param {number[]} nums
* @return {number []}
*/
var insertionSort = function(nums) {
var n = nums.length;
for (var i = 1; i < n; i++) {
var cur = nums[i];//当前要插入的，第一个元素默认插入
for (var j = 0; j < i; j++) {
if (cur < nums[j]) {//找到要插入的位置
for (var k = i; k > j; k--) {//将已经插入过的中的要插入的位置之后的向后移动
nums[k] = nums[k - 1];
}
nums[j] = cur;
break;
}
}
}
return nums;
};
var res = insertionSort([5, 4, 3, 2, 1]);
console.log(res);
【别人家的方法】
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
var count=0;
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;
}
希尔排序（Shell Sort）
希尔排序又叫缩小增量排序。
已知一组无序数据a[0]、a[1]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d < n)，将a[0]、a[0+d]、a[0+2d]……列为第一组，a[1]、a[1+d]、a[1+2d]……列为第二组……，a[d-1]、a[2d-1]、a[3d-1]……列为最后一组依此类推，在各组内用插入排序，然后取d'< d，重复上述操作，直到d=1。
优点：快，数据移动少；
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
/** 希尔排序，升序
* @param {number[]} nums
* @return {number []}
*/
var shellSort = function(nums) {
var n = nums.length;
var increment = Math.floor(n / 2);
while (increment >= 1) {
for (var start = 0; start < increment; start++) {
for (var i = 1; i < Math.ceil(n / increment); i++) {
if (start + increment * i > n - 1) {//下标越界时跳出进行下一次循环
break;
} else {
var cur = nums[start + increment * i];
for (var j = 0; j < i; j++) {//遍历前面的，前面有大的就插入到前面去，在第一个大数之前插入后跳出
if (cur < nums[start + increment * j]) {
for (var k = i; k > j; k--) {
nums[start + increment * k] = nums[start + increment * (k - 1)];
}
nums[start + increment * j] = cur;
break;
}
}
}
}
}
increment = Math.floor(increment / 2);
}
return nums;
};
var res = shellSort([49, 38, 65, 97, 76, 13, 27, 49, 55, 4]);
console.log(res);
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，归并排序将两个已排序的表合并成一个表。
先"分割"再"合并"
/** 归并，升序
* @param {number[]} nums
* @return {number []}
*/
var mergeSort = function(nums) {
var n = nums.length;
if(n<2) return nums;
var middle=Math.floor(n/2),
left=nums.slice(0,middle),
right=nums.slice(middle);
return merge(mergeSort(left),mergeSort(right));
};
//归并两个有序的数组
var merge=function(left,right){
var result=[];
while(left.length>0&&right.length>0){
left[0]<=right[0]?result.push(left.shift()):result.push(right.shift());
}
return result.concat(left).concat(right);
}
var res = mergeSort([5, 4, 3, 2, 1]);
console.log(res);
归并排序
快速排序（Quick Sort）
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。此时基准元素在其排好序后的正确位置。然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
优点：极快，数据移动少；
缺点：不稳定。
/** 快速排序，升序
* @param {number[]} nums
* @return {number []}
*/
var quickSortPre = function(nums) {
var low = 0,
high = nums.length - 1;
return quickSort(nums, low, high);
};
/** 快速排序核心，升序
* @param {number[]} arr
* @param {number} low
* @param {number} high
* @return {number []}
*/
var quickSort = function(arr, low, high) {
if (low < high) {
var pivot = partition(arr, low, high);
console.log("---"+pivot)
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
return arr;
}
var partition = function(arr, low, high) {
//取低的为分界时先判断高位，最后low==high返回其一即可。
//var pivotKey = arr[low];
// while (low < high) {
// while (low < high && arr[high] >= pivotKey) --high;
// [arr[low], arr[high]] = [arr[high], arr[low]];
// while (low < high && arr[low] <= pivotKey) ++low;
// [arr[low], arr[high]] = [arr[high], arr[low]];
// }
// return low;
//取高的为分界时先判断低位。
var pivotKey = arr[high];
while (low < high) {
console.log(arr)
while (low < high && arr[low] <= pivotKey) ++low;
[arr[low], arr[high]] = [arr[high], arr[low]];
while (low < high && arr[high] >= pivotKey) --high;
[arr[low], arr[high]] = [arr[high], arr[low]];
}
return high;
}
var res = quickSortPre([49, 38, 65, 97, 76, 13, 27, 49, 55, 4]);
console.log(res);
网友评论