排序算法以前只知道冒泡排序,两两交换位置,现在有空学习一遍
冒泡排序
冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.有四种实现方式
- 1 正序 正序
- 2 正序 逆序
- 3 逆序 正序
- 4 逆序 逆序
方案一
//先将交换元素部分抽象出来
function swap(i, j, array) {
var temp = array[j];
array[j] = array[i];
array[i] = temp;
}
function bubbleSort(array) {
var length = array.length,
isSwap;
for (var i = 0; i < length; i++) { //正序
isSwap = false;
for (var j = 0; j < length - 1 - i; j++) {
array[j] > array[j + 1] && (isSwap = true) && swap(j, j + 1, array);
}
if (!isSwap) break;
console.log(array)
}
}
bubbleSort([5, 4, 3, 2, 1])
方案二
function bubbleSort(array) {
var length = array.length,
isSwap;
for (var i = 0; i < length; i++) { //正序
isSwap = false;
for (var j = length - 1; j >= i + 1; j--) { //逆序
array[j] < array[j - 1] && (isSwap = true) && swap(j, j - 1, array);
}
if (!isSwap) break;
console.log(array)
}
return array;
}
方案三
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = length - 1; i >= 0; i--) { //逆序
isSwap = false;
for (var j = 0; j < i; j++) { //正序
array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
}
if(!isSwap)
break;
console.log(array)
}
return array;
}
方案四
function bubbleSort(array) {
var length = array.length, isSwap;
for (var i = length - 1; i >= 0; i--) { //逆序
isSwap = false;
for (var j = length - 1; j >= length - 1 - i; j--) { //逆序
array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
}
if(!isSwap)
break;
console.log(array)
}
return array;
}
双向冒泡排序
双向冒泡排序是冒泡排序的一个简易升级版, 又称鸡尾酒排序. 冒泡排序是从低到高(或者从高到低)单向排序, 双向冒泡排序顾名思义就是从两个方向分别排序(通常, 先从低到高, 然后从高到低).
function bothwayBubbleSort(array){
var tail = array.length-1, i, isSwap = false;
for(i = 0; i < tail; tail--){
for(var j = tail; j > i; j--){ //第一轮, 先将最小的数据冒泡到前面
array[j-1] > array[j] && (isSwap = true) && swap(j,j-1,array);
}
i++;
for(j = i; j < tail; j++){ //第二轮, 将最大的数据冒泡到后面
array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
}
}
return array;
}
选择排序
从算法逻辑上看, 选择排序是一种简单且直观的排序算法. 它也是两层循环. 内层循环
就像工人一样, 它是真正做事情的, 内层循环
每执行一遍, 将选出本次待排序的元素中最小(或最大)的一个, 存放在数组的起始位置. 而 外层循环
则像老板一样, 它告诉内层循环
你需要不停的工作, 直到工作完成(也就是全部的元素排序完成).
function selectSort(array) {
var length = array.length, min;
for (var i = 0; i < length - 1; i++) {
min = i;
for (var j = i + 1; j < length; j++) {
array[j] < array[min] && (min = j); //记住最小数的下标
}
min!=i && swap(i,min,array);
}
return array;
}
直接插入排序
它的基本思想是: 将待排序的元素按照大小顺序, 依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去.
function directInsertionSort(array) {
var length = array.length, index, current;
for (var i = 1; i < length; i++) {
index = i - 1; //待比较元素的下标
current = array[i]; //当前元素
while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大
array[index+1] = array[index]; //将待比较元素后移一位
index--; //游标前移一位
//console.log(array);
}
if(index+1 != i){ //避免同一个元素赋值给自身
array[index+1] = current; //将当前元素插入预留空位
//console.log(array);
}
}
return array;
}
折半插入排序
折半插入排序是直接插入排序的升级版. 鉴于插入排序第一部分为已排好序的数组, 我们不必按顺序依次寻找插入点, 只需比较它们的中间值与待插入元素的大小即可.
function binaryInsertionSort(array){
var current, i, j, low, high, m;
for(i = 1; i < array.length; i++){
low = 0;
high = i - 1;
current = array[i];
while(low <= high){ //步骤1&2:折半查找
m = (low + high)>>1;
if(array[i] >= array[m]){//值相同时, 切换到高半区,保证稳定性
low = m + 1; //插入点在高半区
}else{
high = m - 1; //插入点在低半区
}
}
for(j = i; j > low; j--){ //步骤3:插入位置之后的元素全部后移一位
array[j] = array[j-1];
}
array[low] = current; //步骤4:插入该元素
}
return array;
}
希尔排序
希尔排序也称缩小增量排序, 它是直接插入排序的另外一个升级版, 实质就是分组插入排序. 希尔排序以其设计者希尔(Donald Shell)的名字命名, 并于1959年公布.
//形参增加步数gap(实际上就相当于gap替换了原来的数字1)
function directInsertionSort(array, gap) {
gap = (gap == undefined) ? 1 : gap; //默认从下标为1的元素开始遍历
var length = array.length, index, current;
for (var i = gap; i < length; i++) {
index = i - gap; //待比较元素的下标
current = array[i]; //当前元素
while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大
array[index + gap] = array[index]; //将待比较元素后移gap位
index -= gap; //游标前移gap位
}
if(index + gap != i){ //避免同一个元素赋值给自身
array[index + gap] = current; //将当前元素插入预留空位
}
}
return array;
}
function shellSort(array){
var length = array.length, gap = length>>1, current, i, j;
while(gap > 0){
directInsertionSort(array, gap); //按指定步长进行直接插入排序
gap = gap>>1;
}
return array;
}
归并排序
归并排序建立在归并操作之上, 它采取分而治之的思想, 将数组拆分为两个子数组, 分别排序, 最后才将两个子数组合并; 拆分的两个子数组, 再继续递归拆分为更小的子数组, 进而分别排序, 直到数组长度为1, 直接返回该数组为止.
function mergeSort(array) { //采用自上而下的递归方法
var length = array.length;
if(length < 2) {
return array;
}
var m = (length >> 1),
left = array.slice(0, m),
right = array.slice(m); //拆分为两个子数组
return merge(mergeSort(left), mergeSort(right));//子数组继续递归拆分,然后再合并
}
function merge(left, right){ //合并两个子数组
var result = [];
while (left.length && right.length) {
var item = left[0] <= right[0] ? left.shift() : right.shift();//注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
result.push(item);
}
return result.concat(left.length ? left : right);
}
快速排序
快速排序借用了分治的思想, 并且基于冒泡排序做了改进. 它由C. A. R. Hoare在1962年提出. 它将数组拆分为两个子数组, 其中一个子数组的所有元素都比另一个子数组的元素小, 然后对这两个子数组再重复进行上述操作, 直到数组不可拆分, 排序完成.
function quickSort(array, left, right) {
var partitionIndex,
left = typeof left == 'number' ? left : 0,
right = typeof right == 'number' ? right : array.length-1;
if (left < right) {
partitionIndex = partition(array, left, right);//切分的基准值
quickSort(array, left, partitionIndex-1);
quickSort(array, partitionIndex+1, right);
}
return array;
}
function partition(array, left ,right) { //分区操作
for (var i = left+1, j = left; i <= right; i++) {//j是较小值存储位置的游标
array[i] < array[left] && swap(i, ++j, array);//以第一个元素为基准
}
swap(left, j, array); //将第一个元素移至中间
return j;
}
堆排序
堆排序是利用堆这种数据结构所设计的一种排序算法. 它是选择排序的一种. 堆分为大根堆和小根堆. 大根堆要求每个子节点的值都不大于其父节点的值, 即array[childIndex] <= array[parentIndex], 最大的值一定在堆顶. 小根堆与之相反, 即每个子节点的值都不小于其父节点的值, 最小的值一定在堆顶. 因此我们可使用大根堆进行升序排序, 使用小根堆进行降序排序.
function heapAdjust(array, i, length) {//堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < length && array[largest] < array[left]) {
largest = left;
}
if (right < length && array[largest] < array[right]) {
largest = right;
}
if (largest != i) {
swap(i, largest, array);
heapAdjust(array, largest, length);
}
}
function heapSort(array) {
//建立大顶堆
length = array.length;
for (var i = length>>1; i >= 0; i--) {
heapAdjust(array, i, length);
}
//调换第一个与最后一个元素,重新调整为大顶堆
for (var i = length - 1; i > 0; i--) {
swap(0, i, array);
heapAdjust(array, 0, --length);
}
return array;
}
计数排序
计数排序几乎是唯一一个不基于比较的排序算法, 该算法于1954年由 Harold H. Seward 提出. 使用它处理一定范围内的整数排序时, 时间复杂度为O(n+k), 其中k是整数的范围, 它几乎比任何基于比较的排序算法都要快( 只有当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序, 如归并排序和堆排序).
function countSort(array, keyName){
var length = array.length,
output = new Array(length),
max,
min,
simpleArray = keyName ? array.map(function(v){
return v[keyName];
}) : array; // 如果keyName是存在的,那么就创建一个只有keyValue的简单数组
// 获取最大最小值
max = min = simpleArray[0];
simpleArray.forEach(function(v){
v > max && (max = v);
v < min && (min = v);
});
// 获取计数数组的长度
var k = max - min + 1;
// 新建并初始化计数数组
var countArray = new Array(k);
simpleArray.forEach(function(v){
countArray[v - min]= (countArray[v - min] || 0) + 1;
});
// 累加计数,存储不同值的初始下标
countArray.reduce(function(prev, current, i, arr){
arr[i] = prev;
return prev + current;
}, 0);
// 从原数组挨个取值(因取的是原数组的相应值,只能通过遍历原数组来实现)
simpleArray.forEach(function(v, i){
var j = countArray[v - min]++;
output[j] = array[i];
});
return output;
}
桶排序
桶排序即所谓的箱排序, 它是将数组分配到有限数量的桶子里. 每个桶里再各自排序(因此有可能使用别的排序算法或以递归方式继续桶排序). 当每个桶里的元素个数趋于一致时, 桶排序只需花费O(n)的时间. 桶排序通过空间换时间的方式提高了效率, 因此它需要额外的存储空间(即桶的空间).
function bucketSort(array, bucketSize) {
if (array.length === 0) {
return array;
}
var i = 1,
min = array[0],
max = min;
while (i++ < array.length) {
if (array[i] < min) {
min = array[i]; //输入数据的最小值
} else if (array[i] > max) {
max = array[i]; //输入数据的最大值
}
}
//桶的初始化
bucketSize = bucketSize || 5; //设置桶的默认大小为5
var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的个数
buckets = new Array(bucketCount); //创建桶
for (i = 0; i < buckets.length; i++) {
buckets[i] = []; //初始化桶
}
//将数据分配到各个桶中,这里直接按照数据值的分布来分配,一定范围内均匀分布的数据效率最为高效
for (i = 0; i < array.length; i++) {
buckets[~~((array[i] - min) / bucketSize)].push(array[i]);
}
array.length = 0;
for (i = 0; i < buckets.length; i++) {
quickSort(buckets[i]); //对每个桶进行排序,这里使用了快速排序
for (var j = 0; j < buckets[i].length; j++) {
array.push(buckets[i][j]); //将已排序的数据写回数组中
}
}
return array;
}
基数排序
基数排序源于老式穿孔机, 排序器每次只能看到一个列. 它是基于元素值的每个位上的字符来排序的. 对于数字而言就是分别基于个位, 十位, 百位 或千位等等数字来排序. (不明白不要紧, 我也不懂, 请接着往下读)
function radixSort(array, max) {
var buckets = [],
unit = 10,
base = 1;
for (var i = 0; i < max; i++, base *= 10, unit *= 10) {
for(var j = 0; j < array.length; j++) {
var index = ~~((array[j] % unit) / base);//依次过滤出个位,十位等等数字
if(buckets[index] == null) {
buckets[index] = []; //初始化桶
}
buckets[index].push(array[j]);//往不同桶里添加数据
}
var pos = 0,
value;
for(var j = 0, length = buckets.length; j < length; j++) {
if(buckets[j] != null) {
while ((value = buckets[j].shift()) != null) {
array[pos++] = value; //将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
}
}
}
}
return array;
}