导航菜单

电影首发站-JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(上)

前语

算法为王。

算法为王。

想学好前端,先练好内功,内功不可,就算招式练的再花哨,毕竟成不了高手;只要内功深沉者,前端之路才会走得更远。

想学好前端,先练好内功,内功不可,就算招式练的再花哨,毕竟成不了高手;只要内功深沉者,前端之路才会走得更远。

笔者写的 Java 数据结构与算法之美系列用的言语是 Java ,旨在入门数据结构与算法和便利今后温习。

文中包含了十大经典排序算的思维、代码完结、一些比方、杂乱度剖析、动画、还有算法可视化东西。

这应该是现在最全的 Java 十大经典排序算法的解说了吧。

怎么剖析一个排序算法

杂乱度剖析是整个算法学习的精华。

  • 时刻杂乱度: 一个算法履行所耗费的时刻。

  • 空间杂乱度: 运转完一个程序所需内存的巨细。

时刻杂乱度: 一个算法履行所耗费的时刻。

空间杂乱度: 运转完一个程序所需内存的巨细。

学习排序算法,咱们除了学习它的算法原理、代码完结之外,更重要的是要学会怎么点评、剖析一个排序算法。

剖析一个排序算法,要从 履行功率、内存耗费、安稳性三方面下手。

2.1 履行功率

1. 最好状况、最坏状况、均匀状况时刻杂乱度

咱们在剖析排序算法的时刻杂乱度时,要别离给出最好状况、最坏状况、均匀状况下的时刻杂乱度。除此之外,你还要说出最好、最坏时刻杂乱度对应的要排序的原始数据是什么样的。

2. 时刻杂乱度的系数、常数 、低阶

咱们知道,时刻杂乱度反响的是数据规划 n 很大的时分的一个增加趋势,所以它表明的时分会疏忽系数、常数、低阶。

可是实践的软件开发中,咱们排序的或许是 10 个、100 个、1000 个这样规划很小的数据,所以,在对同一阶时刻杂乱度的排序算法功能比照的时分,咱们就要把系数、常数、低阶也考虑进来。

3. 比较次数和交流(或移动)次数

这一节和下一节讲的都是根据比较的排序算法。根据比较的排序算法的履行进程,会触及两种操作,一种是元素比较巨细,另一种是元素交流或移动。

所以,假如咱们在剖析排序算法的履行功率的时分,应该把比较次数和交流(或移动)次数也考虑进去。

2.2 内存耗费

也便是看空间杂乱度。

还需求知道如下术语:

  • 内排序:一切排序操作都在内存中完结;

  • 外排序:由于数据太大,因而把数据放在磁盘中,而排序经过磁盘和内存的数据传输才干进行;

  • 原地排序:原地排序算法,便是特指空间杂乱度是 O(1) 的排序算法。

内排序:一切排序操作都在内存中完结;

外排序:由于数据太大,因而把数据放在磁盘中,而排序经过磁盘和内存的数据传输才干进行;

原地排序:原地排序算法,便是特指空间杂乱度是 O(1) 的排序算法。

2.3 安稳性

  • 安稳:假如待排序的序列中存在值持平的元素,经过排序之后,持平元素之间原有的先后次序不变。比方:a 原本在 b 前面,而 a = b,排序之后,a 仍然在 b 的前面;

  • 不安稳:假如待排序的序列中存在值持平的元素,经过排序之后,持平元素之间原有的先后次序改动。比方:a 原本在 b 的前面,而 a = b,排序之后, a 在 b 的后边;

安稳:假如待排序的序列中存在值持平的元素,经过排序之后,持平元素之间原有的先后次序不变。比方:a 原本在 b 前面,而 a = b,排序之后,a 仍然在 b 的前面;

不安稳:假如待排序的序列中存在值持平的元素,经过排序之后,持平元素之间原有的先后次序改动。比方:a 原本在 b 的前面,而 a = b,排序之后, a 在 b 的后边;

十大经典排序算法(上)

3.1 冒泡排序(Bubble Sort)

思维

  • 冒泡排序只会操作相邻的两个数据。

  • 每次冒泡操作都会对相邻的两个元素进行比较,看是否满意巨细联系要求。假如不满意就让它俩交流。

  • 一次冒泡会让至少一个元素移动到它应该在的方位,重复 n 次,就完结了 n 个数据的排序作业。

冒泡排序只会操作相邻的两个数据。

每次冒泡操作都会对相邻的两个元素进行比较,看是否满意巨细联系要求。假如不满意就让它俩交流。

一次冒泡会让至少一个元素移动到它应该在的方位,重复 n 次,就完结了 n 个数据的排序作业。

特色

  • 长处:排序算法的根底,简略有用易于了解。

  • 缺陷:比较次数多,功率较低。

长处:排序算法的根底,简略有用易于了解。

缺陷:比较次数多,功率较低。

完结

// 冒泡排序(未优化)

constbubbleSort = arr=>{

console.time( '改善前冒泡排序耗时'

constlength = arr.length;

if(length <= 1) return;

// i < length - 1 是由于外层只需求 length-1 次就排好了,第 length 次比较是剩下的。

for( leti = 0; i < length - 1; i++) {

// j < length - i - 1 是由于内层的 length-i-1 到 length-1 的方位现已排好了,不需求再比较一次。

for( letj = 0; j < length - i - 1; j++) {

if(arr[j] > arr[j + 1]) {

consttemp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

console.log( '改善前 arr :', arr);

console.timeEnd( '改善前冒泡排序耗时');

};

优化:当某次冒泡操作现已没有数据交流时,阐明现已到达彻底有序,不用再持续履行后续的冒泡操作。

// 冒泡排序(已优化)

constbubbleSort2 = arr=>{

console.time( '改善后冒泡排序耗时'

constlength = arr.length;

if(length <= 1) return;

// i < length - 1 是由于外层只需求 length-1 次就排好了,第 length 次比较是剩下的。

for( leti = 0; i < length - 1; i++) {

lethasChange = false; // 提早退出冒泡循环的标志位

// j < length - i - 1 是由于内层的 length-i-1 到 length-1 的方位现已排好了,不需求再比较一次。

for( letj = 0; j < length - i - 1; j++) {

if(arr[j] > arr[j + 1]) {

consttemp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

hasChange = true; // 表明有数据交流

}

}

if(!hasChange) break; // 假如 false 阐明一切元素现已到位,没有数据交流,提早退出

}

console.log( '改善后 arr :', arr);

console.timeEnd( '改善后冒泡排序耗时');

};

测验

// 测验

constarr = [ 7, 8, 4, 5, 6, 3, 2, 1];

bubbleSort(arr);

// 改善前 arr : [1, 2, 3, 4, 5, 6, 7, 8]

// 改善前冒泡排序耗时: 0.43798828125ms

constarr2 = [ 7, 8, 4, 5, 6, 3, 2, 1];

bubbleSort2(arr2);

// 改善后 arr : [1, 2, 3, 4, 5, 6, 7, 8]

// 改善后冒泡排序耗时: 0.318115234375ms

剖析

  • 榜首,冒泡排序是原地排序算法吗 ?

    冒泡的进程只触及相邻数据的交流操作,只需求常量级的暂时空间,所以它的空间杂乱度为 O(1),是一个原地排序算法。

  • 第二,冒泡排序是安稳的排序算法吗 ?

    在冒泡排序中,只要交流才干够改动两个元素的前后次序。为了确保冒泡排序算法的安稳性,当有相邻的两个元素巨细持平的时分,咱们不做交流,相同巨细的数据在排序前后不会改动次序。所以冒泡排序是安稳的排序算法。

  • 第三,冒泡排序的时刻杂乱度是多少 ?

    最佳状况:T(n) = O(n),当数据现已是正序时。

    最差状况:T(n) = O(n2),当数据是反序时。

    均匀状况:T(n) = O(n2)。

榜首,冒泡排序是原地排序算法吗 ?

冒泡的进程只触及相邻数据的交流操作,只需求常量级的暂时空间,所以它的空间杂乱度为 O(1),是一个原地排序算法。

第二,冒泡排序是安稳的排序算法吗 ?

在冒泡排序中,只要交流才干够改动两个元素的前后次序。为了确保冒泡排序算法的安稳性,当有相邻的两个元素巨细持平的时分,咱们不做交流,相同巨细的数据在排序前后不会改动次序。所以冒泡排序是安稳的排序算法。

第三,冒泡排序的时刻杂乱度是多少 ?

最佳状况:T(n) = O(n),当数据现已是正序时。

最差状况:T(n) = O(n2),当数据是反序时。

均匀状况:T(n) = O(n2)。

动画

冒泡排序动画

3.2 刺进排序(Insertion Sort)

刺进排序又为分为 直接刺进排序 和优化后的 拆半刺进排序 与 希尔排序,咱们一般说的刺进排序是指直接刺进排序。

一、直接刺进

思维

一般人打扑克牌,收拾牌的时分,都是按牌的巨细(从小到大或许从大到小)收拾牌的,那每摸一张新牌,就扫描自己的牌,把新牌刺进到相应的方位。

刺进排序的作业原理:经过构建有序序列,关于未排序数据,在已排序序列中从后向前扫描,找到相应方位并刺进。

进程

  • 从榜首个元素开端,该元素能够以为现已被排序;

  • 取出下一个元素,在现已排序的元素序列中从后向前扫描;

  • 假如该元素(已排序)大于新元素,将该元素移到下一方位;

  • 重复进程 3,直到找到已排序的元素小于或许等于新元素的方位;

  • 将新元素刺进到该方位后;

  • 重复进程 2 ~ 5。

从榜首个元素开端,该元素能够以为现已被排序;

取出下一个元素,在现已排序的元素序列中从后向前扫描;

假如该元素(已排序)大于新元素,将该元素移到下一方位;

重复进程 3,直到找到已排序的元素小于或许等于新元素的方位;

将新元素刺进到该方位后;

重复进程 2 ~ 5。

完结

// 刺进排序

constinsertionSort = array=> {

constlen = array.length;

if(len <= 1) return

let preIndex, current;

for(let i = 1; i < len; i++) {

preIndex = i - 1; //待比较元素的下标

current = array[i]; //当时元素

while(preIndex >= 0&& array[preIndex] > current) {

//前置条件之一: 待比较元素比当时元素大

array[preIndex + 1] = array[preIndex]; //将待比较元素后移一位

preIndex--; //游标前移一位

}

if(preIndex + 1!= i) {

//防止同一个元素赋值给本身

array[preIndex + 1] = current; //将当时元素刺进预留空位

console.log( 'array :', array);

}

}

returnarray;

};

测验

// 测验

constarray= [ 5, 4, 3, 2, 1];

console. log( "原始 array :", array);

insertionSort( array);

// 原始 array: [5, 4, 3, 2, 1]

// array: [4, 5, 3, 2, 1]

// array: [3, 4, 5, 2, 1]

// array: [2, 3, 4, 5, 1]

// array: [1, 2, 3, 4, 5]

剖析

  • 榜首,刺进排序是原地排序算法吗 ?

    刺进排序算法的运转并不需求额定的存储空间,所以空间杂乱度是 O(1),所以,这是一个原地排序算法。

  • 第二,刺进排序是安稳的排序算法吗 ?

    在刺进排序中,关于值相同的元素,咱们能够挑选将后边呈现的元素,刺进到前面呈现元素的后边,这样就能够坚持原有的前后次序不变,所以刺进排序是安稳的排序算法。

  • 第三,刺进排序的时刻杂乱度是多少 ?

    最佳状况:T(n) = O(n),当数据现已是正序时。

    最差状况:T(n) = O(n2),当数据是反序时。

    均匀状况:T(n) = O(n2)。

榜首,刺进排序是原地排序算法吗 ?

刺进排序算法的运转并不需求额定的存储空间,所以空间杂乱度是 O(1),所以,这是一个原地排序算法。

第二,刺进排序是安稳的排序算法吗 ?

在刺进排序中,关于值相同的元素,咱们能够挑选将后边呈现的元素,刺进到前面呈现元素的后边,这样就能够坚持原有的前后次序不变,所以刺进排序是安稳的排序算法。

第三,刺进排序的时刻杂乱度是多少 ?

最佳状况:T(n) = O(n),当数据现已是正序时。

最差状况:T(n) = O(n2),当数据是反序时。

均匀状况:T(n) = O(n2)。

动画

insertion-sort.gif

二、拆半刺进

刺进排序也有一种优化算法,叫做拆半刺进。

思维

减半刺进排序是直接刺进排序的升级版,鉴于刺进排序榜首部分为已排好序的数组,咱们不用按次序顺次寻觅大豆异黄酮刺进点,只需比较它们的中心值与待刺进元素的巨细即可。

进程

  • 取 0 ~ i-1 的中心点 ( m = (i-1) >> 1 ),array[i] 与 array[m] 进行比较,若 array[i] < array[m],则阐明待刺进的元素 array[i] 应该处于数组的 0 ~ m 索引之间;反之,则阐明它应该处于数组的 m ~ i-1 索引之间。

  • 重复进程 1,每次缩小一半的查找规模,直至找到刺进的方位。

  • 将数组中刺进方位之后的元素悉数后移一位。

  • 在指定方位刺进第 i 个元素。

取 0 ~ i-1 的中心点 ( m = (i-1) >> 1 ),array[i] 与 array[m] 进行比较,若 array[i] < array[m],则阐明待刺进的元素 array[i] 应该处于数组的 0 ~ m 索引之间;反之,则阐明它应该处于数组的 m ~ i-1 索引之间。

重复进程 1,每次缩小一半的查找规模,直至找到刺进的方位。

将数组中刺进方位之后的元素悉数后移一位。

在指定方位刺进第 i 个元素。

注:x >> 1 是位运算中的右移运算,表明右移一位,等同于 x 除以 2 再取整,即 x >> 1 == Math.floor(x/2) 。

注:x >> 1 是位运算中的右移运算,表明右移一位,等同于 x 除以 2 再取整,即 x >> 1 == Math.floor(x/2) 。

// 减半刺进排序

constbinaryInsertionSort = array=> {

constlen = array.length;

if(len <= 1) return;

let current, i, j, low, high, m;

for(i = 1; i < len; i++) {

low = 0;

high = i - 1;

current = array[i];

while(low <= high) {

//进程 1 & 2 : 减半查找

m = (low + high) >> 1; // 注: x>>1 是位运算中的右移运算, 表明右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) .

if( array[i] >= array[m]) {

//值相一同, 切换到高半区,确保安稳性

low = m + 1; //刺进点在高半区

} else{

high = m - 1; //刺进点在低半区

}

}

for(j = i; j > low; j--) {

//进程 3: 刺进方位之后的元素悉数后移一位

array[j] = array[j - 1];

console.log( 'array2 :', JSON.parse(JSON.stringify( array)));

}

array[low] = current; //进程 4: 刺进该元素

}

console.log( 'array2 :', JSON.parse(JSON.stringify( array)));

returnarray;

};

测验

constarray2 = [ 5, 4, 3, 2, 1];

console.log( '原始 array2:', array2);

binaryInsertionSort(array2);

// 原始 array2: [5, 4, 3, 2, 1]

// array2 : [5, 5, 3, 2, 1]

// array2 : [4, 5, 5, 2, 1]

// array2 : [4, 4, 5, 2, 1]

// array2 : [3, 4, 5, 5, 1]

// array2 : [3, 4, 4, 5, 1]

// array2 : [3, 3, 4, 5, 1]

// array2 : [2, 3, 4, 5, 5]

// array2 : [2, 3, 4, 4, 5]

// array2 : [2, 3, 3, 4, 5]

// array2 : [2, 2, 3, 4, 5]

// array2 : [1, 2, 3, 4, 5]

留意:和直接刺进排序类似,减半刺进排序每次交流的是相邻的且值为不同的元素,它并不会改动值相同的元素之间的次序,因而它是安稳的。

三、希尔排序

希尔排序是一个均匀时刻杂乱度为 O(n log n) 的算法,会在下一个章节和 归并排序、快速排序、堆排序 一同讲,本文就不展开了。

3.3 挑选排序(Selection Sort)

思路

挑选排序算法的完结思路有点类似刺进排序,也分已排序区间和未排序区间。可是挑选排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的结尾。

进程

  • 首先在未排序序列中找到最小(大)元素,寄存到排序序列的开始方位。

  • 再从剩下未排序元素中持续寻觅最小(大)元素,然后放到已排序序列的结尾。

  • 重复第二步,直到一切元素均排序完毕。

首先在未排序序列中找到最小(大)元素,寄存到排序序列的开始方位。

再从剩下未排序元素中持续寻觅最小(大)元素,然后放到已排序序列的结尾。

重复第二步,直到一切元素均排序完毕。

完结

constselectionSort = array=> {

constlen = array.length;

let minIndex, temp;

for(let i = 0; i < len - 1; i++) {

minIndex = i; 电影首发站-JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(上)

for(let j = i + 1; j < len; j++) {

if( array[j] < array[minIndex]) {

// 寻觅最小的数

minIndex = j; // 将最小数的索引保存

}

}

temp = array[i];

array[i] = array[minIndex];

array[minIndex] = temp;

console.log( 'array: ', array);

}

returnarray;

};

测验

// 测验

constarray= [ 5, 4, 3, 2, 1];

console.log( '原始array:', array);

selectionSort( array);

// 原始 array: [5, 4, 3, 2, 1]

// array: [1, 4, 3, 2, 5]

// array: [1, 2, 3, 4, 5]

// array: [1, 2, 3, 4, 5]

// array: [1, 2, 3, 4, 5]

剖析

  • 榜首,挑选排序是原地排序算法吗 ?

    挑选排序空间杂乱度为 O(1),是一种原地排序算法。

  • 第二,挑选排序是安稳的排序算法吗 ?

    挑选排序每次都要找剩下未排序元素中的最小值,并和前面的元素交流方位,这样破坏了安稳性。所以,挑选排序是一种不安稳的排序算法。

  • 第三,挑选排序的时刻杂乱度是多少 ?

    无论是正序仍是逆序,挑选排序都会遍历 n2 / 2 次来排序,所以,最佳、最差和均匀的杂乱度是相同的。

    最佳状况:T(n) = O(n2)。

    最差状况:T(n) = O(n2)。

    均匀状况:T(n) = O(n2)。

榜首,挑选排序是原地排序算法吗 ?

挑选排序空间杂乱度为 O(1),是一种原地排序算法。

第二,挑选排序是安稳的排序算法吗 ?

挑选排序每次都要找剩下未排序元素中的最小值,并和前面的元素交流方位,这样破坏了安稳性。所以,挑选排序是一种不安稳的排序算法。

第三,挑选排序的时刻杂乱度是多少 ?

无论是正序仍是逆序,挑选排序都会遍历 n2 / 2 次来排序,所以,最佳、最差和均匀的杂乱度是相同的。

最佳状况:T(n) = O(n2)。

最差状况:T(n) = O(n2)。

均匀状况:T(n) = O(n2)。

动画

selection-sort.gif

3.4 归并排序(Merge Sort)

思维

排序一个数组,咱们先把数组从中心分红前后两部分,然后对前后两部别离离排序,再将排好序的两部分兼并在一同,这样整个数组就都有序了。

归并排序选用的是电影首发站-JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(上)分治思维。

分治,望文生义,便是分而治之,将一个大问题分解成小的子问题来处理。小的子问题处理了,大问题也就处理了。

merge-sort-example.png

注:x >> 1 是位运算中的右移运算,表明右移一位,等同于 x 除以 2 再取整,即 x >> 1 === Math.floor(x / 2) 。

注:x >> 1 是位运算中的右移运算,表明右移一位,等同于 x 除以 2 再取整,即 x >> 1 === Math.floor(x / 2) 。

完结

constmergeSort = arr=>{

//选用自上而下的递归办法

constlen = arr.length;

if(len < 2) {

returnarr;

}

// length >> 1 和 Math.floor(len / 2) 等价

letmiddle = Math.floor(len / 2),

left = arr.slice( 0, middle),

right = arr.slice(middle); // 拆分为两个子数组

returnmerge(mergeSort(left), mergeSort(right));

};

constmerge = (left, right) =>{

constresult = [];

while(left.length && right.length) {

// 留意: 判别的条件是小于或等于,假如仅仅小于,那么排序将不安稳.

if(left[ 0] <= right[ 0]) {

result.push(left.shift);

} else{

result.push(right.shift);

}

}

while(left.length) result.push(left.shift);

while(right.length) result.push(right.shift);

returnresult;

};

测验

// 测验

constarr = [ 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

console.time( '归并排序耗时');

console.log( 'arr :', mergeSort(arr));

console.timeEnd( '归并排序耗时');

// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

// 归并排序耗时: 0.739990234375ms

剖析

  • 榜首,归并排序是原地排序算法吗 ?

    这是由于归并排序的兼并函数,在兼并两个有序数组为一个有序数组时,需求凭借额定的存储空间。实践上,虽然每次兼并操作都需求请求额定的内存空间,但在兼并完结之后,暂时拓荒的内存空间就被开释掉了。在恣意时刻,CPU 只会有一个函数在履行,也就只会有一个暂时的内存空间在运用。暂时内存空间最大也不会超越 n 个数据的巨细,所以空间杂乱度是 O(n)。所以,归并排序不是原地排序算法。

  • 第二,归并排序是安稳的排序算法吗 ?

    merge 办法里边的 left[0] <= right[0] ,确保了值相同的元素,在兼并前后的先后次序不变。归并排序是安稳的排序办法。

  • 第三,归并排序的时刻杂乱度是多少 ?

    从功率上看,归并排序可算是排序算法中的佼佼者。假定数组长度为 n,那么拆分数组共需 logn 步,又每步都是一个一般的兼并子数组的进程,时刻杂乱度为 O(n),故其归纳时刻杂乱度为 O(n log n)。

    最佳状况:T(n) = O(n log n)。

    最差状况:T(n) = O(n log n)。

    均匀状况:T(n) = O(n log n)。

榜首,归并排序是原地排序算法吗 ?

这是由于归并排序的兼并函数,在兼并两个有序数组为一个有序数组时,需求凭借额定的存储空间。实践上,虽然每次兼并操作都需求请求额定的内存空间,但在兼并完结之后,暂时拓荒的内存空间就被开释掉了。在恣意时刻,CPU 只会有一个函数在履行,也就只会有一个暂时的内存空间在运用。暂时内存空间最大也不会超越 n 个数据的巨细,所以空间杂乱度是 O(n)。所以,归并排序不是原地排序算法。

第二,归并排序是安稳的排序算法吗 ?

merge 办法里边的 left[0] <= right[0] ,确保了值相同的元素,在兼并前后的先后次序不变。归并排序是安稳的排序办法。

第三,归并排序的时刻杂乱度是多少 ?

从功率上看,归并排序可算是排序算法中的佼佼者。假定数组长度为 n,那么拆分数组共需 logn 步,又每步都是一个一般的兼并子数组的进程,时刻杂乱度为 O(n),故其归纳时刻杂乱度为 O(n log n)。

最佳状况:T(n) = O(n log n)。

最差状况:T(n) = O(n log n)。

均匀状况:T(n) = O(n log n)。

动画

merge-sort.gif

3.5 快速排序 (Quick Sort)

快速排序的特色便是快,并且功率高!它是处理大数据最快的排序算法之一。

思维

  • 先找到一个基准点(一般指数组的中部,然后数组被该基准点分为两部分,顺次与该基准点数据比较,假如比它小,放左面;反之,放右边。

  • 左右别离用一个空数组去存储比较后的数据。

  • 最终递归履行上述操作,直到数组长度 <= 1;

先找到一个基准点(一般指数组的中部,然后数组被该基准点分为两部分,顺次与该基准点数据比较,假如比它小,放左面;反之,放右边。

左右别离用一个空数组去存储比较后的数据。

最终递归履行上述操作,直到数组长度 <= 1;

特色:快速,常用。

缺陷:需求别的声明两个数组,浪费了内存空间资源。

完结

办法一:

constquickSort1 = arr=>{

if(arr.length <= 1) {

returnarr;

}

//取基准点

constmidIndex = Math.floor(arr.length / 2

//取基准点的值,splice(index,1) 则回来的是含有被删去的元素的数组。

constvalArr = arr.splice(midIndex, 1);

constmidIndexVal = valArr[ 0];

constleft = []; //寄存比基准点小的数组

constright = []; //寄存比基准点大的数组

//遍历数组,进行判别分配

for( leti = 0; i < arr.length; i++) {

if(arr[i] < midIndexVal) {

left.push(arr[i]); //比基准点小的放在左面数组

} else{

right.push(arr[i]); //比基准点大的放在右边数组

}

}

//递归履行以上操作,对左右两个数组进行操作,直到数组长度为 <= 1

returnquickSort1(left).concat(midIndexVal, quickSort1(right));

};

constarray2 = [ 5, 4, 3, 2, 1];

console.log( 'quickSort1 ', quickSort1(array2));

// quickSort1: [1, 2, 3, 4, 5]

办法二:

// 快速排序

constquickSort = (arr, left, right) =>{

letlen = arr.length,

partitionIndex;

left = typeofleft != 'number'? 0: left;

right = typeofright != 'number'? len - 1: right;

if(left < right) {

partitionIndex = partition(arr, left, right);

quickSort(arr, left, partitionIndex - 1);

quickSort(arr, partitionIndex + 1, right);

}

returnarr;

};

constpartition = (arr, left, right) =>{

//分区操作

letpivot = left, //设定基准值(pivot)

index = pivot + 1;

for( leti = index; i <= right; i++) {

if(arr[i] < arr[pivot]) {

swap(arr, i, index);

index++;

}

}

swap(arr, pivot, index - 1);

returnindex - 1;

};

constswap = (arr, i, j) =>{

lettemp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

};

测验

// 测验

constarray= [ 5, 4, 3, 2, 1];

console.log( '原始array:', array);

constnewArr = quickSort( array);

console.log( 'newArr:', newArr);

// 原始 array: [5, 4, 3, 2, 1]

// newArr: [1, 4, 3, 2, 5]

剖析

  • 榜首,快速排序是原地排序算法吗 ?

    由于 partition 函数进行分区时,不需求许多额定的内存空间,所以快排是原地排序算法。

  • 第二,快速排序是安稳的排序算法吗 ?

    和挑选排序类似,快速排序每次交流的元素都有或许不是相邻的,因而它有或许打破本来值为相同的元素之间的次序。因而,快速排序并不安稳。

  • 第三,快速排序的时刻杂乱度是多少 ?

    极点的比方:假如数组中的数据本来现已是有序的了,比方 1,3,5,6,8。假如咱们每次挑选最终一个元素作为 pivot,那每次分区得到的两个区间都是不平等的。咱们需求进行大约 n 次分区操作,才干完结快排的整个进程。每次分区咱们均匀要扫描大约 n / 2 个元素,这种状况下,快排的时刻杂乱度就从 O(nlogn) 退化成了 O(n2)。

    最佳状况:T(n) = O(n log n)。

    最差状况:T(n) = O(n2)。

    均匀状况:T(n) = O(n log n)。

榜首,快速排序是原地排序算法吗 ?

由于 partition 函数进行分区时,不需求许多额定的内存空间,所以快排是原地排序算法。

第二,快速排序是安稳的排序算法吗 ?

和挑选排序类似,快速排序每次交流的元素都有或许不是相邻的,因而它有或许打破本来值为相同的元素之间的次序。因而,快速排序并不安稳。

第三,快速排序的时刻杂乱度是多少 ?

极点的比方:假如数组中的数据本来现已是有序的了,比方 1,3,5,6,8。假如咱们每次挑选最终一个元素作为 pivot,那每次分区得到的两个区间都是不平等的。咱们需求进行大约 n 次分区操作,才干完结快排的整个进程。每次分区咱们均匀要扫描大约 n / 2 个元素,这种状况下,快排的时刻杂乱度就从 O(nlogn) 退化成了 O(n2)。

最佳状况:T(n) = O(n log n)。

最差状况:T(n) = O(n2)。

均匀状况:T(n) = O(n log n)。

动画

quick-sort.gif

回答开篇问题

快排和归并用的都是分治思维,递推公式和递归代码也十分类似,那它们的差异在哪里呢 ?

快速排序与归并排序

能够发现:

  • 归并排序的处理进程是由下而上的,先处理子问题,然后再兼并。

  • 而快排正好相反,它的处理进程是由上而下的,先分区,然后再处理子问题。

  • 归并排序虽然是安稳的、时刻杂乱度为 O(nlogn) 的排序算法,可是它对错原地排序算法。

  • 归并之所以对错原地排序算法,首要原因是兼并函数无法在原地履行。

  • 快速排序经过规划奇妙的原地分区函数,能够完结原地排序,处理了归并排序占用太多内存的问题。

归并排序的处理进程是由下而上的,先处理子问题,然后再兼并。

而快排正好相反,它的处理进程是由上而下的,先分区,然后再处理子问题。

归电影首发站-JavaScript 数据结构与算法之美 - 十大经典排序算法汇总(上)并排序虽然是安稳的、时刻杂乱度为 O(nlogn) 的排序算法,可是它对错原地排序算法。

归并之所以对错原地排序算法,首要原因是兼并函数无法在原地履行。

快速排序经过规划奇妙的原地分区函数,能够完结原地排序,处理了归并排序占用太多内存的问题。

还没完毕

这篇文章只列举了十大经典排序算法的一半哦。

笔者为了写好这系列的文章,花费了很多的业余时刻,边学边写,边写边修正,前后历时差不多 2 个月,入门级的文章总算是写完了。

ps:记住看下一篇Oo(今天推送第四条)

二维码