排序算法—javascript

1.冒泡排序（Bubble Sort）：

通过不断交换相邻元素将最大（或最小）的元素逐渐移动到列表的末尾。

代码实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            // 与相邻元素比较
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

复杂度分析

• 时间复杂度：最好时间复杂度 O(n)，平均时间复杂度 O(n²)
• 空间复杂度：O(1)

2. 插入排序（Insertion Sort）：

逐个将元素插入已排序的部分，将未排序的元素依次插入到正确的位置。

代码实现

function insertionSort(arr) {
    let n = arr.length;
    let preIndex, current;
    // 从第二个元素开始
    for (let i = 1; i < n; i++) {
        preIndex = i - 1;
        current = arr[i];
        // 从当前位置向前扫描， 如果前面元素的大于当前的值，则将前面元素向后挪动，继续向前扫描
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        // 将当前元素插入对应位置
        arr[preIndex + 1] = current;
    }
    return arr;
}

复杂度分析

• 时间复杂度：最好时间复杂度 O(n)，最坏时间复杂度O(n²)，平均时间复杂度 O(n²)
• 空间复杂度：O(1)

3. 选择排序（Selection Sort）：

在未排序序列中找到小元素，存放到排序序列的起始位置，然后在从剩余的未排序的元素中寻找最小元素，然后放到已排序的序列的末尾，依次类推，直到所有元素均排序完毕。

代码实现

function selectionSort(arr) {
  let length = arr.length,
      indexMin
  for(let i = 0; i < length - 1; i++) {
    indexMin = i
    // 遍历一次 找到最小元素的索引
    for(let j = i; j < length; j++) {
      if(arr[indexMin] > arr[j]) {
        indexMin = j
      }
    }
    // 交换位置，把最小元素放到已排序的序列的末尾
    if(i !== indexMin) {
      let temp = arr[i]
      arr[i] = arr[indexMin]
      arr[indexMin] = temp
    }
  }
}

复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

4. 快速排序（Quick Sort）：

快排的过程简单的说只有三步：

• 首先从序列中选取一个数作为基准数
• 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 partition）
• 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现：

• 1，创建两个指针分别指向数组的最左端以及最右端
• 2，在数组中任意取出一个元素作为基准
• 3，左指针开始向右移动，遇到比基准大的停止
• 4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
• 5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
• 6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

复杂度分析

• 时间复杂度：O(n㏒₂n)
• 空间复杂度：O(n㏒₂n)

5. 归并排序（Merge Sort）：

将列表不断分割成更小的子列表，然后逐个合并子列表以获得最终的排序列表。

function mergeSort(arr) {
  let array = mergeSortRec(arr)
  return array
}

// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后合并小数组
function mergeSortRec(arr) {
  let length = arr.length
  if(length === 1) {
    return arr
  }
  let mid = Math.floor(length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length)
  return merge(mergeSortRec(left), mergeSortRec(right))
}

// 顺序合并两个小数组left、right 到 result
function merge(left, right) {
  let result = [],
      ileft = 0,
      iright = 0
  while(ileft < left.length && iright < right.length) {
    if(left[ileft] < right[iright]){
      result.push(left[ileft ++])
    } else {
      result.push(right[iright ++])
    }
  }
  while(ileft < left.length) {
    result.push(left[ileft ++])
  }
  while(iright < right.length) {
    result.push(right[iright ++])
  }
  return result
}

复杂度分析

• 时间复杂度：O(n㏒₂n)
• 空间复杂度：O(n)

6. 堆排序（Heap Sort）：

将列表构建成最大堆或最小堆，然后反复从堆中取出根节点（最大或最小元素），并重新构建堆。

function heapSort(items) {
    // 构建大顶堆
    buildHeap(items, items.length-1)
    // 设置堆的初始有效序列长度为 items.length - 1
    let heapSize = items.length - 1
    for (var i = items.length - 1; i > 1; i--) {
        // 交换堆顶元素与最后一个有效子元素
        swap(items, 1, i);
        // 有效序列长度减 1
        heapSize --;
        // 堆化有效序列(有效序列长度为 currentHeapSize，抛除了最后一个元素)
        heapify(items, heapSize, 1);
    }
    return items;
}

// 原地建堆
// items: 原始序列
// heapSize: 有效序列长度
function buildHeap(items, heapSize) {
    // 从最后一个非叶子节点开始，自上而下式堆化
    for (let i = Math.floor(heapSize/2); i >= 1; --i) {    
        heapify(items, heapSize, i);  
    }
}
function heapify(items, heapSize, i) {
    // 自上而下式堆化
    while (true) {
        var maxIndex = i;
        if(2*i <= heapSize && items[i] < items[i*2] ) {
            maxIndex = i*2;
        }
        if(2*i+1 <= heapSize && items[maxIndex] < items[i*2+1] ) {
            maxIndex = i*2+1;
        }
        if (maxIndex === i) break;
        swap(items, i, maxIndex); // 交换 
        i = maxIndex; 
    }
}  
function swap(items, i, j) {
    let temp = items[i]
    items[i] = items[j]
    items[j] = temp
}

7. 希尔排序（Shell Sort）：

通过将列表分成多个子列表，分别进行插入排序，逐渐减小子列表的间隔，直到最后一次使用插入排序。

function shellSort(arr) {
    let n = arr.length;
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < n; 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;
        }
    }
    return arr;
}