数据结构中的各种排序方法小结(JS实现)

function bubbleSort(array) {      for (var i = 0; i < array.length; i++) {        for (var j = array.length; j > 0; j--) {          if (array[j] < array[j - 1]) {            var temp = array[j - 1];            array[j - 1] = array[j];            array[j] = temp;          }        }        /* 输出结果 */        document.write("这是第 + (i + 1) + "次循环・，结果为:");        for (var k = 0; k < array.length; k++) {          document.write(array[k] + ",");        }        document.write("<br />");        /* 输出结果结束 */      }    }

function insertSort(array) {      var temp;      for (var i = 1; i < array.length; i++) {        var temp = array[i];        for (var j = i; j > 0 && temp < array[j - 1]; j--) {          array[j] = array[j - 1];        }        array[j] = temp        /* 输出结果 */        document.write("第? + i + "遍排序的结果是:")        for (var n = 0; n < array.length; n++) {          document.write(array[n] + ",");        }        document.write("<br />")        /* 输出结果结束 */      }    }

function selectSort(array) {      var min, temp; ;      for (var i = 0; i < array.length; i++) {        min = i;        for (var j = i + 1; j < array.length; j++) {          if (array[min] > array[j])            min = j;        }        if (min != i) {          temp = array[i];          array[i] = array[min];          array[min] = temp;        }        /* 输出结果 */        document.write("第 + i + "遍排序的结果是:")        for (var n = 0; n < array.length; n++) {          document.write(array[n] + ",");        }        document.write("<br />")        /* 输出结果结束 */      }    }

function shallSort(array) {      var increment = array.length;      var i      var temp; //暂存      var count = 0;      do {        increment = Math.floor(increment / 3) + 1;        for (i = increment; i < array.length; i++) {          if (array[i] < array[i - increment]) {            temp = array[i];            for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) {              array[j + increment] = array[j];            }            array[j + increment] = temp;            /* 输出结果 */            count++;            document.write("<br />第 + count + "遍排序的结果是:")            for (var n = 0; n < array.length; n++) {              document.write(array[n] + ",");            }            /* 输出结果结束 */          }        }      }      while (increment > 1)    }

function heapSort(array) {      var temp;      var i;      for (i = Math.floor(array.length / 2); i >= 0; i--) {        heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆      }      for (i = array.length - 1; i >= 0; i--) {        /*把根节点交换出去*/        temp = array[i];        array[i] = array[0];        array[0] = temp;        /*余下的数组继续构建成大顶堆*/        heapAdjust(array, 0, i - 1);        /* 输出结果 */        document.write("<br />第 + (array.length - i).toString() + "遍排序的结果是:")        for (var n = 0; n < array.length; n++) {          document.write(array[n] + ",");        }        /* 输出结果结束 */      }    }    //要调整的子树    //start为数组开始下标    //max是数组结束下标    function heapAdjust(array, start, max) {      var temp, j;      temp = array[start];//temp是根节点的值      for (j = 2 * start; j < max; j *= 2) {        if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标          ++j;        }        if (temp >= array[j])          break;        array[start] = array[j];        start = j;      }      array[start] = temp;    }

//source源数组    //dest目标数组    //s起始下标    //t目标下标    function mSort(source, dest, s, t) {      var m; //取中间值      var dest2 = new Array();      if (s == t) {        dest[s] = source[s];             }      else {        m = Math.floor((s + t) / 2);        mSort(source, dest2, s, m);        mSort(source, dest2, m+1 , t);        merge(dest2, dest, s, m, t);        /* 输出结果 */        document.write("<br />第 + ++count + "遍排序的结果是:")        for (var n = 0; n < dest.length; n++) {          document.write(array[n] + ",");        }        /* 输出结果结束 */      }    }        //将两个数组按照从小到大的顺序融合    //source原数组    //dest排序后的数组    //s第一个下标    //m第二个数组下标    //总长度    function merge(source, dest, s, m, n) {      for (var j = m+1, k = s; j <= n && s <= m; k++) {        if (source[s] < source[j]) {          dest[k] = source[s++];        }        else {          dest[k] = source[j++];        }      }              //将剩余排不完的有序数组加入到dest的末端        if (s <= m) {          for (var l = 0; l <= m - s; l++) {            dest[k + l] = source[s+l];          }        }        if (j <= n) {          for (var l = 0; l <= n - j; l++) {            dest[k + l] = source[j+l];          }              }    }

var count = 0;    function quickSort(array, low, high) {      var temp;            if (low < high) {        var keypoint = QuickSortHelp(array, low, high);        count++;        document.write("<br />第台? + count + "遍括?排?序ò的?结á果?是?:")        for (var l = 0; l < array.length; l++) {          document.write(array[l] + ",");        }        quickSort(array, low, keypoint - 1);        quickSort(array, keypoint + 1, high);                }    }    function QuickSortHelp(array, low, high) {      while (low < high) {        while (low < high && array[low] <= array[high]) {          high--;        }        temp = array[low];        array[low] = array[high];        array[high] = temp;        while (low < high && array[low] <= array[high]) {          low++        }        temp = array[low];        array[low] = array[high];        array[high] = temp;      }      return low;    }