数据结构与算法--排序算法

常见的五种排序算法：
冒泡排序；选择排序；插入排序；归并排序；快速排序；
前三种是基本排序算法，后两个是高级的排序算法；

冒泡排序

最慢 的排序算法之一，数据值会像气泡一样从数组的一段漂浮到另一端

基本思路：

1.依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数
2.对除了最后一个之外的数重复第一步，直到只剩一个数

图形展示：

代码实现：

function bubbleSort(myArray){
  var len = myArray.length;
  var i;
  var j;
  var stop;

  for (i = 0; i < len - 1; i++){
    for (j = 0, stop = len - 1 - i; j < stop; j++){
      if (myArray[j] > myArray[j + 1]){
        swap(myArray, j, j + 1);
      }
    }
  }
  return myArray;
}
//交换数组两个元素
function swap(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}

//测试一下
var dataStore = [1,8,3,2,9,5,4,7];
console.log(bubbleSort(dataStore));

选择排序

基本思路：

1.找出最小的数，和第一个交换位置
2.在剩下的数中，找出最二小的数，和第二个交换位置
3.依次类推，排出顺序

图形展示：

代码实现：

function selectionSort(myArray){
    var len = myArray.length,
        min;

    for (i=0; i < len; i++){
        // 将当前位置设为最小值
        min = i;
        // 检查数组其余部分是否更小
        for (j=i+1; j < len; j++){
            if (myArray[j] < myArray[min]){
                min = j;
            }
        }
        // 如果当前位置不是最小值，将其换为最小值
        if (i != min){
            swap(myArray, i, min);
        }
    }
    return myArray;
}

//交换数组两个元素
function swap(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}

//测试一下
var dataStore = [1,8,3,2,9,5,4,7];
console.log(selectionSort(dataStore));

插入排序

基本思路：

1.把数组分为[已排序]和[未排序]两部分
2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

图形展示：

代码实现：

function insertionSort(myArray) {
    var len     = myArray.length,     // 数组的长度
        value,                      // 当前比较的值
        i,                          // 未排序部分的当前位置
        j;                          // 已排序部分的当前位置

    for (i=1; i < len; ++i) {
        // 储存当前位置的值,未排序部分的第一个值
        value = myArray[i];

        j = i;
        /*
         * 已排序部分从后往前一个个的和value比较
         * 如果大于value，就往后移动一位
         */
        while(j>0&&myArray[j-1]>value){
          myArray[j] = myArray[j-1];
          j--;
        }
        //j是value最终插入到有序部分的索引
        myArray[j] = value;
    }
    return myArray;
}

//测试一下
var dataStore = [1,8,3,2,9,5,4,7];
console.log(insertionSort(dataStore));

归并排序（分而治之）

基本思路：

1.不断将数组对半分，直到每个数组只有一个
2.将分出来的部分重新合并
3.合并的时候按顺序排列

图形展示：

代码实现：

// 被拆分的数组重新合并
function merge(left, right) {
    var result = [],
        left_index = 0,
        right_index = 0;

    // 将两个数组合并
    // 合并的时候按从小到大的顺序
    //本例子18进18出，32进23出，1823进1238出
    while (left_index < left.length && right_index < right.length) {
        if (left[left_index] < right[right_index]) {
            result.push(left[left_index++]);
        } else {
            result.push(right[right_index++]);
        }
    }

    // 和其他数组拼接，上一个while中差最大的一个没有排序，这里给加到最后
    // var result1 = result.concat(left.slice(left_index)).concat(right.slice(right_index));
    return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}

function mergeSort(myArray) {
    // 只有一个数的时候退出递归
    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left = myArray.slice(0, middle),
        right = myArray.slice(middle);

    // 递归
    // 不断拆分只到一个数组只有一个数
    // var result1 = merge(mergeSort(left), mergeSort(right));
    return merge(mergeSort(left), mergeSort(right));
}

//测试一下
var dataStore = [1, 8, 3, 2, 9, 5, 4, 7];
console.log(mergeSort(dataStore));

快速排序

基本思路：

1.以一个数为基准(第一个数或者中间的数都可以)，比基准小的放到左边，比基准大的放到右边
2.再按此方法对这两部分数据分别进行快速排序（递归进行）
3.不能再分后退出递归，并将数组合并

图形展示：

代码实现：

var quickSort = function (myArray) {　　
// 当被分的数组只剩一个时，退出递归
if (myArray.length <= 1) {
    return myArray;
}

//这里选择中间的值为基准值，当然也可以选择别的为基准值，比如选择第一个数
// 中间基准值的index
var pivotIndex = Math.floor(myArray.length / 2);　　
// 基准值
var pivot = myArray.splice(pivotIndex, 1)[0];　　

var left = [];　　
var right = [];　　
// 小的放左边，大的放右边
for (var i = 0; i < myArray.length; i++) {　　　　
    if (myArray[i] < pivot) {　　
        left.push(myArray[i]);　
    } else {
        right.push(myArray[i]);　
    }　　
}　　

// 递归
// 把数组合并在一起
return quickSort(left).concat([pivot], quickSort(right));
};

//测试一下
var dataStore = [1, 8, 3, 2, 9, 5, 4, 7];
console.log(quickSort(dataStore));

GitHub: GitHub