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

新技术一直在不断变化，掌握一些基础是未来学习不断更新的技术的坚实基础。近来闲来无事,为了温习一下从前学的数据结构，将数据结构中的排序算法用JS实现了一遍，并在本文末尾处嵌入了DEMO。

简单排序

冒泡排序

冒泡排序是最简单排序算法,时间复杂度为n的平方,代码如下:

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 />");        /* 输出结果结束 */      }    }

直接插入排序

直接插入排序也属于简单排序算法,时间复杂度也为n的平方，但性能略好于冒泡排序，代码如下:

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 />")        /* 输出结果结束 */      }    }

选择排序

选择排序也属于简单排序算法，时间复杂度也为n的平方，性能同样略微好于冒泡排序，代码如下:

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 />")        /* 输出结果结束 */      }    }

复杂排序

希尔排序

希尔排序是插入排序的升级，1959年希尔通过将简单排序中两两比较改为设置步长跳跃式比较而突破了n的平方的时间复杂度,希尔排序根据步长的不同时间复杂度由最好的nlogn到最坏的n的平方。代码如下:

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)    }