冒泡排序

////////////////////////////////////////////////////////////////
// bubble sort
function ArrayList(){
    // 私有变量
    var arr = [];

    // 将数组中i，j位置的数组进行交换
    var swap = function(i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // add element
    this.insert = function(item) {
        arr.push(item);
    }

    // to string
    this.toString = function(){
        //  数组中的join() 方法默认是按照 "," 进行分割的
        return arr.join();
    }

    // v1 : bubble sort（注意：i, j两个变量都是从0开始的）
    this.bubbleSort = function(){
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            // 内层循环从第一位一直迭代到倒数第二位
            for (var j = 0; j < len - i; j++) {
                // 只要前面的元素比后面的元素大的话，就去直接交换
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1);
                }
            }
        }
    }




    // v2 : 从内循环减去外循环已经跑过的轮数，可以避免循环中所有不必要的比较
    this.bubbleSort = function (){
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            for (var j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1);
                }
            }
        }
    }

}3


/*
 * 创建一个无序数组
 * @ size
 * */
function createNoneSortedArray(size){
    var arr = new ArrayList();
    for (var i = size; i > 0; i--) {
        // 直接给数组初始化一个逆序的数组序列
        arr.insert(i);
    }
    return arr;
}



///////////////////////////////////////////////////////////////////////
// 测试
var arr = createNoneSortedArray(5);
console.log(arr, arr.toString());
// bubble sort
arr.bubbleSort();
console.log(arr.toString());

插入排序

//////////////////////////////////////////////////////////////////////////////////////
// insert sort
function ArrayList(){
    var arr = [];

    var swap = function(i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    this.insert = function (item){
        arr.push(item);
    }

    this.toString = function(){
        return arr.join();
    }

    // v1 : insert sort
    this.insertSort = function(){
        var len = arr.length;
        // 每次直接从当前元素前面的元素进行比较交换
        // 假设用户的手中刚开始的时候已经有了一张扑克牌了
        for (var i = 1; i < len; i++) {
            for (var j = i; j > 0; j--) {
                if (arr[j - 1] > arr[j]) {
                    swap(j - 1, j);
                }/* else {
                    break;
                }*/
            }
        }
    }

    // v2 : 不使用swap函数进行交换，直接使用原地交换的方式进行排序
    this.insertSort = function(){
        var len = arr.length;
        for (var i = 1; i < len; i++) {
            // 1. 先把当前的元素缓存起来
            var e = arr[i];
            // 2. 保存当前元素e应该插入到的位置j
            var j;
            // 注意点：
            // 1. 插入排序的内层循环必须和这个元素e进行比较，而不是和前面的元素进行比较
            // 2. 比较大小的代码必须放在这个内层for循环之内进行比较
            for (j = i; j > 0 && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
            // 3. 执行完毕内层循环之后，j的位置已经是当前的目标插入位置了
            arr[j] = e;
        }
    }
}


function createNoneSortArray(size){
    var arr = new ArrayList();
    for (var i = size; i > 0; i--) {
        arr.insert(i);
    }
    return arr;
}



///////////////////////////////////////////////////////////////////////////////
// 测试
var arr = createNoneSortArray(5);
console.log(arr.toString());
arr.insertSort();
console.log(arr.toString());

选择排序

//////////////////////////////////////////////////////////////////////////////////////
// select sort
function ArrayList(){
    var arr = [];

    var swap = function(i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    this.insert = function (item){
        arr.push(item);
    }


    this.toString = function(){
        return arr.join()
    }

    //  select sort
    this.selectSort = function(){
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            var minIndex = i;
            // 每次从当前位置以后的元素选择一个最小的元素放在第i个位置上面
            for (var j = i; j < len; j++) {
                if (arr[j] < arr[i]) {
                    minIndex = j;
                }
            }
            // 如果当前位置和原始的最小值的标定下标是一样的话，就不处理
            if (i !== minIndex)
                swap(i, minIndex);
        }
    }
}


// 创建一个无序数组序列
function createNoneSortArray(size){
    var arr = new ArrayList();
    for (var i = size; i > 0; i--) {
        arr.insert(i);
    }
    return arr;
}



///////////////////////////////////////////////////////////////////////////////////////
// 测试
var arr = createNoneSortArray(5);
console.log(arr.toString());
arr.selectSort();
console.log(arr.toString());

归并排序

//////////////////////////////////////////////////////////////////////////////////////
// merge sort
function ArrayList(){
    var arr = []

    var swap = function(i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    this.insert = function (item){
        arr.push(item);
    }

    this.toString = function (){
        return arr.join();
    }


    ////////////////////////////////////////////////////////////////////
    // merge sort 辅助函数
    // 开始对区间[l, middle], [middle + 1, r]区间的元素进行归并
    var __merge = function(arr, l, middle, r){
        console.log('merge aray start : ', arr, l, middle, r);
        // 1. 开辟一个临时空间，把原始的数组复制到这个新的数组里面
        // 数组深度克隆： arr.slice(), arr.concat(), for循环， fo (var item in arr)循环
        var aux = arr.concat();
        for (var i = l; i <= r; i++) {
            aux[i - l] = arr[i];
            console.log('copy ', arr[i], aux[i], i, r);
        }

        console.log('aux array now is ', aux, arr);

        // 2. 开始进行归并(i, j位置的初始化)
        var i = l, j = middle + 1;
        for (var k = l; k <= r; k++) {
            // 这里需要进行越界的检查啊
            if (i > middle) {
                // 开始去处理右边的
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            }

            // 遍历[l, r]区间内的元素(开始依次比较左右区间内的元素的大小，找出一个最小值, 放在第k个位置)
            else if (aux[i - l] < aux[j - l]) {
                arr[k] = aux[i - l];
                i++;
            } else {
                arr[k] = aux[j - l];
                j++;
            }

        }
    }


    // 递归使用归并排序算法对arr[l, r]这个区间范围内的数据进行排序
    var __mergeSort = function(arr, l, r){
        console.log('sort ……', l, r);
        // 1. 递归终止条件(l必须始终大于r的)
        if (l >= r)
            return ;
        // 2. 计算数组中间的位置
        var middle = Math.floor(l + (r - l) / 2);
        console.log('middle now is ', middle);
        // 2. 开始对左边的区间元素进行归并排序[l, middle]
        __mergeSort(arr, l, middle);
        // 3. 开始对右边的区间元素进行归并排序[middle + 1, r]
        __mergeSort(arr, middle + 1, r);
        console.log('loading……', l, r, middle);

        // 4. 排序完成之后，开始进行归并
        __merge(arr, l, middle, r);

        return arr;
    }

    // v1 : merge sort
    this.mergeSort =  function(){
        // 对区间[0, n - 1]的元素进行归并排序
        arr = __mergeSort(arr, 0, arr.length - 1);         // 将数组中的数据修改为最新的数据信息
        return arr;
    }


}



function createNoneSortArray(size){
    var arr = new ArrayList();
    for (var i = size; i > 0; i--) {
        arr.insert(i);
    }
    return arr;
}



///////////////////////////////////////////////////////////////////////////////////////
// 测试
var arr = createNoneSortArray(5);
console.log('init array : ', arr.toString());
arr.mergeSort();
console.log('caculate result : ', arr.toString());

快速排序

//////////////////////////////////////////////////////////////////////////////////////
// quick sort
function ArrayList(){
    var arr = [];

    var swap = function(i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    this.insert = function (item){
        arr.push(item);
    }

    this.toString = function (){
        return arr.join();
    }

    ///////////////////////////////////////////////////////////////////////////////////////
    // quick sort
    // 求出数组arr在区间[l, r]范围的下标p位置，使得p满足条件, arr[l , p - 1] < arr[p], arr[p + 1, r] > arr[p]
    var __partition = function(arr, l, r){
        // 1. 选择数组中的第一个元素作为标定点
        var v = arr[l];
        // 2. 初始化变量的初始位置, arr[l + 1, i] < v, arr[j, r] >= v
        var i = l + 1, j = r;

        // 3. 开始循环
        while (true) {
            // i 向后移动
            while (i <= r && arr[i] < v){
                i++;
            }

            // j 向前移动
            while (j >= l && arr[j] > v) {
                j--;
            }

            // 交换数据之前需要先来处理一下元素的条件
            if (i > j) {
                break;
            }

            // 此处说明遇到了第一个arr[i] > v && arr[j] < v的元素，直接交换即可
            swap(i, j);

            // 交换完毕之后，开始进入下一个循环
            i++;
            j--;
        }

        // 执行完毕之后，将v元素放在正确的位置
        swap(l, j);
        // 最终j的位置就是标定点的位置
        return j;
    }


    // 实现对区间arr[l, r] 范围内的元素使用快速排序
    var __quickSort = function(arr, l, r){
        // 1. 递归终止的条件
        if (l >= r) {
            return;
        }

        // 2. 开始求出p的位置，使得数组满足条件arr[l, p - 1] < arr[p], arr[p + 1, r] > arr[p]
        var p = __partition(arr, l, r);
        // 3. 继续对arr[l, p - 1], arr[p + 1, r]区间的元素使用快速排序
        __quickSort(arr, l, p - 1);
        __quickSort(arr, p + 1, r);
    }


    this.quickSort = function(){
        // 使用递归实现快速排序
        __quickSort(arr, 0, arr.length - 1);
    }






    function quickSort(arr) {
      __quickSort(arr, 0, arr.length - 1)
    }

    function __quickSort(arr, l, r) {
      if (l >= r) {
          return;
      }

      let p = __partition(arr, l, r);
      __quickSort(arr, l, p - 1);
      __quickSort(arr, P + 1, r)
    }

    function __partition() {
      let v = arr[l];
      let i = l + 1, j = r;
      while (true) {
          while () 
      } 
    }
}


function createNoneSortArray(size){
    var arr = new ArrayList();
    for (var i = size; i > 0; i--) {
        arr.insert(i);
    }
    return arr;
}



//////////////////////////////////////////////////////////////////////////////////
// 测试
var arr = createNoneSortArray(5);
console.log(arr.toString());
arr.quickSort();
console.log(arr.toString());