学习笔记 - Weekly_Task01 - 《CodeLearning》

冒泡排序
插入排序
- 直接插入
- 希尔排序
  - 1.思路
  - 2.实现参考
选择排序
快速排序
基数排序
归并排序

冒泡排序

Weekly_Task01 - 图1

1.思路

比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素向左移动至正确的顺序，

2.实现参考

function bubbleSort(array, compareFn = defaultCompare) {         
  const { length } = array; 
  for (let i = 0; i < length; i++) { // 外循环 {1}
    for (let j = 0; j < length - 1; j++) { // {2}
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // {3}
        swap(array, j, j + 1); 
      }     
    }   
  }    
  return array;
}

【注释】
{1}i最后一个值刚好是最后一项的索引，i代表了循环轮数
{2}j最后一个值是倒数第二项的索引，每相邻的的两个数都要作比较，依次往右组合；
每循环结束（即回到外循环），就会确认一位大的数放在后面
{3}若当前项比下一项大，则交换

//创建的swap函数
function swap(array, a, b) {
/ const temp = array[a];
array[a] = array[b];
array[b] = temp; / // 经典方式
[array[a], array[b]] = [array[b], array[a]]; // ES2015 的方式
}
【注释】每次新一轮外循环的时候，未排序的左侧数值算一个新的序列

3.测试

function createNonSortedArray(size) {
const array = [];
for (let i = size; i > 0; i—) {
array.push(i);
}
return array;
}
let array = createNonSortedArray(5);
console.log(array.join());
array = bubbleSort(array);
console.log(array.join());

4.复杂度

时间复杂度都是O（n2 ）
空间复杂度是O（1）（因为只定义了一个辅助变量）

5.实践
```
var nums = [5,4,3,2,1];
const {length} = nums;
for (let i = 0 ;i<length;i++){
for (let j=0;j<length;j++){
  if (nums[j]>nums[j+1]){
    let temp = nums[j];
    nums[j] = nums[j+1];
    nums[j+1] = temp  
   }
 }
}
```
插入排序

直接插入

1.思路
每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较，小的在前大的在后（类似于扑克牌的整理，前面的已经整理好了——从左到右由小至大）。

2.实现参考
```
function insertionSort(array, compareFn = defaultCompare) {
const { length } = array; 
let temp;
for (let i = 1; i < length; i++) { // {1}
 let j = i; // {2}
 temp = array[i]; // {3}
 while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {      
// {4}
   array[j] = array[j - 1]; // {5}
   j--; //{6}
 }
 array[j] = temp; // {7}
}
return array;
};
```
【注释】
{1}迭代数组来给第 i 项找到正确的位置(从第二个位置的索引开始，因为认为第一项已经排序)
{2}用i的值来初始化一个辅助变量j
{3}并也将该待插入值存储在一个临时变量中(便于之后将其插入到正确的位置上)
{4}条件：只要符合“变量j比0大，且前面的值大于后面一个的值”（前者bigger than 后者）
{5}如果符合上述条件，那么就把这个前面的较大的值移到当前待插入数字的位置上，即后一个位置
{6}这里j减小1，是为了下面能够将待插入但是比前一位要小的新数值赋到前一位上

3.复杂度
时间复杂度
- 所以如果数组本来就是有序的，则数组的最好情况下时间复杂度为O（n）
- 如果数组是[5,4,3,2,1]这种，想要排成从小到大，则每一趟前面的数都要往后移，一共要执行（n-1 + n-2 + … + 2 + 1 = n (n-1) / 2 =0.5 n2 - 0.5 * n次，去掉低次幂及系数，所以最坏情况下时间复杂度为O（n2）
- 平均时间复杂度(n+n2 )/2，所以平均时间复杂度为O（n2）
空间复杂度
- 插入排序算法只需要两个变量暂存当前数，以及下标，与n的大小无关，所以空间复杂度为：O（1）
  4.实践

直接插入

var nums = [1,3,8,5,7,2,9];
let temp;
const {length} = nums;
for (let i = 1;i<length;i++){
let j = i;
while(j>0&&nums[j]<nums[j-1]){ //使用while是为了将内循环往前推进
  temp = nums[j-1];
  nums[j-1] = nums[j];
  nums[j] = temp;
  j--
}
}
console.log(nums)

希尔排序

又称为缩小增量排序，是直接插入排序算法的加强版。（一个数叫做一个记录）

1.思路

按步长 gap 分组（第1个，第1+n个，第1+2个。。。），对每组记录采用直接插入排序方法进行排序——同一组里面，较小的数字放在前面
当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
（增量一般用数组长度的一半取整为初始值，如下面第一趟gap1=N/2, gap2=gap1/2）
希尔排序.png

2.实现参考

var arr = [3,5,7,1,4,25,9,8];
let len = arr.length;
for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
for (let i = gap; i < len; i++) {
  let j = i;
  let current = arr[i];
  while(j - gap >= 0 && current < arr[j - gap]) {
    arr[j] = arr[j - gap];
    j = j - gap;
  }
  arr[j] = current;
}
}

选择排序

Weekly_Task01 - 图4

1.思路

找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

2.实现参考

function selectionSort(array, compareFn = defaultCompare) {
 const { length } = array; 
 let indexMin;
 for (let i = 0; i < length - 1; i++) { 
   indexMin = i; // {1}
   for (let j = i; j < length; j++) { // 内循环
     if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) { // {2}
         indexMin = j; // {3}
       }
     }
     if (i !== indexMin) { // {5}
       swap(array, i, indexMin);
     }
   }
  return array;
};

【注释】
{1}假设本迭代轮次的的第一个值为数组最小值 (最小值对应的索引为i)
{2}比较是否位置 j 的值比当前最小值小
{3}如果位置 j 的值比当前最小值小（未排序中的最小），则二者交换
{4}当内循环结束，将得出数组第 n 小的值
{5}如果该最小值和原最小值不同，则交换其值。

3.复杂度

时间复杂度都是O（n2 ）

空间复杂度是O（1）（因为只定义了两个辅助变量，且与n无关）

4.实践

var nums = [5,4,3,2,1,11,33,3,44];
const {length} = nums;
let minIndex;
for (let i = 0;i<length-1;i++) {
  minIndex = i;
  for (let j = i+1;j<length;j++){
      if(nums[minIndex]>nums[j]){
          minIndex = j;
      };
  };
  if (i!==minIndex){
      swap(nums,i,minIndex)
  }
  console.log(nums)
};
function swap(nums,a,b){
  [nums[a],nums[b]]=[nums[b],nums[a]]
};

【注意！！】最后那个if语句是要放在第二个for循环（即内循环外面的），否则有一些数无法进行正确的排序

快速排序

Weekly_Task01 - 图5

1.思路

分治思想。

分治法 的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解只需关注最小问题该如何求解，和如何去递归。
步骤

(1) 从数组中选择一个值作为主元（枢纽，相当于定一个点），也就是数组中间的那个值。
(2) 划分操作：创建两个指针，左边一个指向数组第一个值，右边一个指向数组最后一个值。移动指针进行两个指针所对着的
(3) 算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复上述两个步骤，直至数组已完全排序。
递归思想。

2.实现参考

（1）。。。

function quickSort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
};
//创建quick函数
function quick(array, left, right, compareFn) {
 let index; // {1}
 if (array.length > 1) { 
 index = partition(array, left, right, compareFn); // {2}
 if (left < index - 1) { 
 quick(array, left, index - 1, compareFn); 
 }
 if (index < right) { 
 quick(array, index, right, compareFn); 
 }
 }
 return array;
};

【注释】
{1}index便于将子数组分离为较小值数组和较大值数组
{2}第一次调用面向整个数组

（2）划分过程

function partition(array, left, right, compareFn) {
 const pivot = array[Math.floor((right + left) / 2)]; //{1}
 let i = left; 
 let j = right; 
 while (i <= j) { //{2}
 while (compareFn(array[i], pivot) === Compare.LESS_THAN) { 
 i++;
 }
 while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) { 
 j--;
 }
 if (i <= j) { 
 swap(array, i, j); 
   i++;
 j--;
 }
 }
 return i; 
}

【注释】
{1}选择主元（最简单如示例，选）
{2}只要两指针没有相互交错则符合循环条件，执行“划分”操作
{2}

3.复杂度

最坏即冒泡

时间复杂度：
- 平均时间复杂度为O（nlog2n）
空间复杂度：
- 平均空间复杂度为O（log2n）

基数排序

1.思路

先以个位数的大小来对数据进行排序，（已排好个位的数形成一个新的排列），接着（对新的排列）以十位数的大小来多数进行排序，以此类推
（上图相当于每一次排序都将该轮位数数值相同的数放进同一个桶中）

MSD —— 从高位开始排序
LSD —— 从低位开始排序（以此为例）

基数排序.gif

2.实现参考

var radix = 16; // 基数，可以为任何数，越大趟数越小，但是桶数越多，最好根据最大数字进行定义。
function _roundSort(arr, round, radix) {
  var buckets = new Array(radix);
  //创建空桶
  for (let i = 0; i < radix; i++) {
    buckets[i] = [];
  }
  // 将数组中的数放进对应的桶子中
  for (let i = 0; i < arr.length; i++) {
    //求余数，并以余数为分类的判断标准
    let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;
    buckets[remainder].push(arr[i]);
  }
  // 将数组重新根据桶子进行排序
  var index = 0;
  for (let i = 0; i < buckets.length; i++) {
    for (let j = 0; j < buckets[i].length; j++) {
      arr[index++] = buckets[i][j];
    }
  }
}
//多次桶排序
function radixSort(arr, round) {
  for (let i = 1; i <= round; i++) {
    _roundSort(arr, i, radix);
  }
  return arr;
}
console.log(radixSort([10,5,5,50,0,155,4622,5,1,4,2154], 4)); //测试

3.复杂度

空间复杂度：O（n+k）
时间复杂度：O（n*k）

归并排序

归并排序.gif

1.思路

采用分治法，先使每个子序列有序，再使子序列段间有序，最后将子序列合并
（合并两个有序表合并成一个有序表，称为2-路归并。）

2.实现参考

function mergeSort(arr) {
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    //分出两个子序列（以中间那个数为界）
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right)); 
}
//下面调用的shift（）函数有助于while的终止
function merge(left, right) {
    var result = [];
    while(left.length>0 && right.length>0) {
        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());
    return result;
}

3.复杂度

空间复杂度：O(n)
时间复杂度：O(nlog2n)

Weekly_Task01

冒泡排序

1.思路

2.实现参考

3.测试

4.复杂度

5.实践

插入排序

直接插入

1.思路

2.实现参考

3.复杂度

4.实践

希尔排序

1.思路

2.实现参考

选择排序

1.思路

2.实现参考

3.复杂度

4.实践

快速排序

1.思路

2.实现参考

3.复杂度

基数排序

1.思路

2.实现参考

3.复杂度

归并排序

1.思路

2.实现参考

3.复杂度