• 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 计数排序(counting sort)
  • 基数排序(radix sort)
  • 希尔排序
  • 堆排序
  • 桶排序

先行条件

构造一个数组列表函数

  1. function ArrayList(){
  2.   this.array=[];
  4.   //插入元素
  5.   ArrayList.prototype.insert=function(item){
  6.     this.array.push(item);
  7.   }
  9.   //以字符串输出数组列表元素
  10.   ArrayList.prototype.toString=function(){
  11.     return this.array.join("-");
  12.   }
  14. }
  16. var list = new ArrayList(); //实例化
  18.     list.insert(3);
  19.     list.insert(6);
  20.     list.insert(4);
  21.     list.insert(2);
  22.     list.insert(84);
  23.     list.insert(966);
  24.     list.insert(487);
  26. //交换两个位置的数据
  27.     ArrayList.prototype.swap = function (pos1, pos2) {
  28.       let temp = this.array[pos1];
  29.       this.array[pos1] = this.array[pos2];
  30.       this.array[pos2] = temp;
  31.     }

冒泡排序 Bubble sort

对未排序的元素从头到尾依次比较相邻两个元素的关系

  2. ArrayList.prototype.buubleSort = function () {
  3.       //获取数组长度
  4.       let length = this.array.length;
  6.       for (let j = length - 1; j >= 0; j--) {
  7.         for (let i = 0; i < j; i++) {
  8.           if (this.array[i] > this.array[i + 1]) {
  9.             this.swap(i, i + 1);
  10.           }
  11.         }
  12.       }
  13.     }
  15. console.log(list.toString())
  16. list.buubleSort();
  17. console.log(list.toString())

排序前：3-6-4-2-84-966-487
排序后：2-3-4-6-84-487-966

比较次数

大O表示法 排序算法 - 图1
公式：N*(N-1)/2

交换次数

大O表示法 排序算法 - 图2
公式：N*(N-1)/4

选择排序Select sort

选定第一个索引位置，依次跟后面的元素依次比较
如果后面的元素小于第一个索引的元素，则交换位置
经过一轮比较后就可以确认第一个位置是最小的
然后再使用同样的方法把剩下的元素比较

  1. ArrayList.prototype.selectSort=function(){
  2.     let length=this.array.length //获取数组列表长度
  4.   //遍历数组的每一项元素
  5.   //length-1 就是数组的最后一项，而最后一项不用比较的，因为已经排序过了
  6.   for(let j=0;j<length-1;j++){
  7.     let min=j; //定义变量min存储里层循环获取到的最小元素索引
  8.     /*
  9.     再次遍历数组元素 初始值等于min+1 因为外层循环的时候会把min等于外层循环索引
  10.     而外层循环当前索引是不用在里层循环遍历的 之前的元素已经正确的排号位置了 所以直接跳过
  11.     j
  12.     4 9 5 6 81 2
  13.     m
  14.       i 
  15.     */
  16.       for(let i=min+1;i<length;i++){ 
  17.         if(this.array[min]>this.array[i]){  //比较min索引的元素和遍历的每一个元素 哪个大
  18.           min=i;  //如果Min>里层遍历的元素 就把里层当前循环的索引赋值给min 
  19.       }
  20.     }
  21.     this.swap(min,j);  //交换元素
  22.   } 
  24. }
  26. list.selectSort();
  27. console.log(list.toString());

结果输出：2-3-4-6-84-487-966

比较字数

大O表示法 排序算法 - 图3
公式：N*(N-1)/2

交换次数

大O表示法 排序算法 - 图4
公式：N-1

插入排序 Insert sort

插入排序的核心是局部有序
在一个数组中 选择其中一个作为标记元素
被标记元素左边所有元素已经排好顺序
意味着有一部分已经排好序，还有一部分是没有排序的

  1. ArrayList.prototype.insertSort=function(){
  2.     let length=this.array.length; //获取数组长度
  4.     /*
  5.     遍历数组里的每一个元素 从1开始，因为要示左边为以排序好，选择元素插入到左边排序好的位置
  6.     */
  7.     for(let i=1;i<length;i++){ 
  8.         let j=i;  //j 算是一个指针 指遍历左边排序好的元素
  9.         let temp=this.array[i]  //temp 存储当前循环索引位置的元素数据
  11.         //用while循环 因为不知道插到哪个位置 
  12.         //循环的条件是 如果数组j-1就是上一个元素大于temp(是当前循环索引位置的元素数据) 就执行循环体的指令
  13.         while(this.array[j-1]>temp&&j>0){
  14.             //把当前循环索引位置的元素数据换成上一个元素数据
  15.             //例如：6 3 9 2    i=3 temp=3 j=3 j-1=6 j=j-1 就是j=6
  16.             this.array[j]=this.array[j-1];
  17.                //指针指向上一个元素
  18.             j--
  19.         }
  21.         //插入temp的数据到j的位置
  22.         this.array[j]=temp;
  24.     }
  25. }

比较次数

公式：N*(N-1)/4
大O表示法：

复制次数

公式：N*(N-1)/2

希尔排序 Shell’s Sort

是插入排序的一种高效的进化版，并且效率比插入排序更快
通过指定的间隔来交换数组元素，尽量让最小的排到最前面，最后的尽量排到后面

间隔选择 Shell原稿

N / 2 N=数组长度
如果N=100 向下取整
100/2=50 50/2=25 25/2=12 12/2=6 6/2=3 3/2=1

  1. ArrayList.prototype.ShellSort = function () {
  2.       let length=this.array.length; //获取数组长度
  3.       let gap=Math.floor(length/2); //间隔增量 为数组的长度除以2
  5.     //循环，只要gap大于或者等于1 就执行循环体内的指令
  6.       while(gap>=1){
  7.           //遍历数组的每一个元素
  8.         for(let i=gap;i<length;i++){
  9.           let j=i; //把i复制给j j相当于指针
  10.           let temp=this.array[i]; //把i的元素复制给temp 因为等一下i的元素会变
  12.            /*
  13.            循环，当j-gap大于temp的时候 j一开始是和gap相等，j-gap=0 如果索引为0的元素大于temp
  14.            以及j>gap-1 这是为了防止越界
  15.            */
  16.           while(this.array[j-gap]>temp&&j>gap-1){
  17.               //就把j-gap的元素给j 执行到这里说明j-gap索引的元素大于j的元素 所以要调换位置 把大放到右边
  18.             this.array[j]=this.array[j-gap];
  19.               //j重新赋值 向左退gap步
  20.             j-=gap;
  21.           }
  22.           this.array[j]=temp;
  23.         }
  24.           //每次gap都除以2 向下取整
  25.         gap=Math.floor(gap/2);
  26.       }
  27.     }

例子：数组元素 [2 6 4 3 84 966 487]
0 1 2 3 4 5 6
2 6 4 3 84 966 487

let gap=Math.floor(length/2);
gap=7/2 3.5向下取整3

while(gap>=1)
while循环当gap<1的时候停止

for(let i=gap;i遍历数组的每一个元素 从索引为gap的开始 也就是3 依次递增

let j=i;
每次循环都生命一个 j 指针变量 初始化为i j是用来向gap的左边递减寻找上一个gap的

let temp=this.array[i];
以及temp变量，存储 i 的元素值 因为等一下交换了元素后 i的值可能会变

while(this.array[j-gap]>temp){
this.array[j]=this.array[j-gap];
}
循环当数组的j-gap索引位置的元素 大于 temp 的时候就把j-gap的元素赋值给j

j-=gap;
每次j-=gap 相当于往左边进gap步 以到达下一个gap

this.array[j]=temp
最内层循环结束后就就把temp赋值给j

再次执行遍历循环

gap=Math.floor(gap/2);
遍历循环结束后 每次gap/2 向下取整 直到gap<=1就跳出循环
然后再次执行最外层while循环

快速排序Quick sort

重要的思想：分而治之

  1. ArrayList.prototype.quickSort = function (arr) {
  3.       let length = arr.length;  //获取数组的长度
  5.     //如果数组的长度小于1 就不用排序，直接返回数组
  6.       if (length <= 1) {
  7.         return arr;
  8.       }
  10.       let left = []; //存放小于基准的元素
  11.       let right = []; //存放大于基准的元素
  12.       let povit = arr[0]; //基准选取数组的一个元素
  14.     //遍历数组的每一个元素
  15.       for (let i = 1; i < length; i++) {
  16.           //小于基准的就放到left数组
  17.         if (arr[i] < povit) {
  18.           left.push(arr[i]);
  19.         } else {
  20.          //大于基准的就放到right数组
  21.           right.push(arr[i]);
  22.         }
  23.       }
  25.     //递归调用方法
  26.     //因为方法返回的是排序后数组 所以用排序后 小于基准的数组 合并 基准元素 以及排序后 大于基准的元素数组
  27.       return this.quickSort(left).concat(povit, this.quickSort(right));
  29.     }

平均效率

大O表示法：O(N*logN)