wordpress发号系统巢湖seo推广

学习笔记：coderwhy的JavaScript实现数据结构与算法的课程
其他章节笔记链接
1. 重要性
2. 线性结构
3. 哈希表
4. 树结构
5. 图结构
6. 排序和搜索【本文】

（六）排序算法

准备工作：封装一个列表
代码如下：

	// 创建列表类function ArrayList() {// 属性this.array = [];// 方法// 将数据可以插入到数组中的方法ArrayList.prototype.insert = function (item) {this.array.push(item);};// toStringArrayList.prototype.toString = function () {return this.array.join('-');};// 交换两个位置的数据ArrayList.prototype.swap = 	function(m,n){var temp = this.array[m];this.array[m] = this.array[n];this.array[n] = temp;}// 实现排序算法};// 测试类var list = new ArrayList();// 插入元素list.insert(66);list.insert(12);list.insert(88);list.insert(7);list.insert(100);list.insert(5);list.insert(566);list.insert(23);alert(list);

1. 简单排序

1.1 冒泡排序

1.1.1 简介

1.1.2 思路

1.1.3 代码实现

// 冒泡排序ArrayList.prototype.bubblesort = function () {// 1. 获取数组的长度var length = this.array.length;for (var i = 0; i < length-1; i++){for (var j = length - 1; j >= 0; j-- ){if (this.array[j] > this.array[j+1]){// 交换两个数据this.swap(j,j+1);}}};};

1.1.4 测试代码

	// 验证冒泡排序list.bubblesort();alert(list);

1.1.5 效率

(1) 比较次数：n(n-1)/2 O(n^2)
(2) 交换次数：n(n-1)/4 O(n^2)

1.2 选择排序

1.2.1 思路

1.2.2 代码实现

// 选择排序ArrayList.prototype.selectionSort = function () {// 1. 获取数组的长度var length = this.array.length;// 2.外层循环：从0开始读取数据for (var j = 0; j < length - 1 ; j++){// 内层循环： 从i+1开始和后面的数据进行比较var min = j;for (var i = j ; i < length; i++){if(this.array[min] > this.array[i]){min = i;}};this.swap(min,j);}};

1.2.3 测试代码

    // 验证选择排序list.selectionSort();alert(list);

1.2.4 效率

(1) 比较次数：n(n-1)/2 O(n^2)
(2) 交换次数：n-1 O(n)

1.3 插入排序

1.3.1 简介

1.3.2 思路

局部有序：

1.3.3 效率分析

1.3.5 效率分析

(1) 比较次数：n(n-1)/4 O(n^2)
(2) 交换次数：n-1 O(n)

1.3.6 代码实现

 // 插入排序ArrayList.prototype.insertSort = function () {// 1. 获取数组的长度var length = this.array.length;// 2. 外层循环：从第一个位置开始读取数据，像前面局部有序进行插入for (var i = 1 ; i < length ; i++){// 3. 内层循环：获取i位置的元素，和前面的数据依次进行比较。var temp =  this.array[i];var j = i ;while (this.array[j-1] > temp && j > 0) {this.array[j] = this.array [j-1];j--;}// 4. 将j位置的数据放置tempthis.array[j] = temp;}};

1.3.7 测试代码

   // 验证插入排序list.insertSort();alert(list);

2. 高级排序

2.1 希尔排序

2.1.1 简介

2.1.2 思路

2.1.3 选择合适的增量

2.1.4 代码实现

// 希尔排序ArrayList.prototype.shellSort = function () {// 1. 获取数组的长度var length = this.array.length;// 2. 初始化的增量（gap -> 间隔/间隙)var gap = Math.floor(length/2);// 3. while循环（gap）不断减小while(gap >= 1){// 4. 以gap作为间隔，进行分组，对分组进行插入操作for (var i = gap ; i < length ; i++){var temp = this.array[i];var j = i;while (this.array[j - gap] > temp && j > gap - 1 ) {this.array[j] = this.array[j - gap];j -= gap;}// 5. 将j位置的元素赋值tempthis.array[j] = temp;};// 6. 增量变化gap = Math.floor(gap / 2);};};

2.1.5 测试代码

    list.shellSort();alert(list);

2.1.6 效率

2.2 快速排序

2.2.1 简介

2.2.2 重要性

2.2.3 枢纽选择

2.2.4 代码实现

 // 快速排序// 1. 选择枢纽ArrayList.prototype.medium = function (left,right) {// 1. 取出中间的位置var center = Math.floor((left + right)/2);// 2. 判断大小，并且进行交换if ( this.array[left] > this.array[center]){this.swap(left , center);};if (this.array[left] > this.array[right]){this.swap(left , right);};if (this.array[center] > this.array[right]){this.swap(center , right);};// 3.将center换到right-1的位置this.swap(center , right - 1)return this.array[right - 1]};// 2. 快速排序的实现ArrayList.prototype.quickSort = function () {this.quick(0 , this.array.length - 1);};ArrayList.prototype.quick= function (left , right) {// 1. 结束条件if ( left >= right ){return};// 2. 获取枢纽var pivot = this.medium(left , right);// 3. 定义变量，用于当前找到的位置var i = left;var j = right - 1;// 4. 开始进行交换while (i<j){while(this.array[++i] < pivot){};while (this.array[--j] > pivot){};if (i < j){this.swap(i , j);}else{break;};}// 5. 将枢纽放置在正确的位置，i的位置this.swap(i ,right-1);// 6. 分而治之this.quick(left, i-1);this.quick(i + 1, right);};

2.2.5 测试代码

    list.quickSort();alert(list);

2.2.6 效率

2.3 插入排序

3. 补充知识：大O表示法

3.1 简介

3.2 常见的大O表示函数

3.3 推导大O表示法的方法

—————————————————————————————————————————
如果我的文章能帮你节约20秒，就请你为我的文章点个赞吧！