/* * 1.插入排序（直接插入排序） * 思想：将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录增1的有序表。默认将第一个元素看为有序表，然后依次插入后边的元素 * 注意：这里插入元素的时候默认的策略是从后向前看，找第一个比自己小的；而不是从前向后看，找第一个比自己大的， * 时间复杂度：O(n^2)         空间复杂度：O(1)         稳定性：稳定 * */Array.prototype.sortGuo1 = function() {  for (var i = 1; i < this.length; i++) {    var tem = this[i];    for (var j = i - 1; j >= 0 && tem < this[j]; j--) {      this[j + 1] = this[j]; //循环后移比自己tem大的数据    }    this[j + 1] = tem; //找到第一个比自己tem小的位置j，将值插入到该位置后面  }  return this;};var arr1 = [311, 32, 32, 3, 346, 457, 56, 7, 56, 8, 679, 78];alert(arr1.sortGuo1());/* * 2.插入排序（希尔排序）（缩小增量排序） * 思想：希尔排序也是插入排序的一种，是直接针对插入排序进行改进的，该方法又称为"缩小增量排序"。 * 时间复杂度：O(n^2)      空间复杂度：O(1)      稳定性：不稳定 * */Array.prototype.sortGuo2 = function() {  var step = Math.floor(this.length / 2); //初始增量  while (step >= 1) {    for (var i = step; i < this.length; i++) {      var tem = this[i];      for (var j = i - step; j >= 0 && tem < this[j]; j--) {        this[j + step] = this[j]; //循环后移比自己tem大的数据      }      this[j + step] = tem; //找到第一个比自己tem小的位置j，将值插入到该位置后面    }    step = Math.floor(step / 2); //缩小增量step  }  return this;};var arr2 = [311, 32, 32, 3, 346, 457, 56, 7, 56, 8, 679, 78];alert(arr2.sortGuo2());/* * 3.选择排序 * 思想：每一趟排序将会选择出最小的值放在前面 * 时间复杂度：O(n^2)         空间复杂度：O(1)         稳定性：不稳定 * */Array.prototype.sortGuo3 = function() {  for (var i = 0; i < this.length - 1; i++) {    for (var j = i + 1; j < this.length; j++) {      if (this[j] < this[i]) {        var tem = this[i];        this[i] = this[j];        this[j] = tem;      }    }  }  return this;};var arr3 = [311, 32, 32, 3, 346, 457, 56, 7, 56, 8, 679, 78];alert(arr3.sortGuo3());/* * 4.交换排序（冒泡排序） * 思想：重复走访过要排序的序列，从后往前，一次比较两个元素，如果他们的顺序错误就将他们进行交换，每一次冒上来的最小的到剩余待排序序列的顶部。 * 时间复杂度：O(n^2)         空间复杂度:O(1)         稳定性：稳定 * */Array.prototype.sortGuo4 = function() {  for (var i = 0; i < this.length - 1; i++) //n-1趟冒泡，每趟冒出最小的  {    for (var j = this.length - 1; j > i; j--) //n-1 n-2 ...1 比较次数依次递减    {      if (this[j] < this[j - 1]) {        var tem = this[j - 1];        this[j - 1] = this[j];        this[j] = tem;      }    }  }  return this;};var arr4 = [311, 32, 32, 3, 346, 457, 56, 7, 56, 8, 679, 78];alert(arr4.sortGuo4());/* * 5.交换排序（快速排序） * 思想：通过一趟排序将待排记录分割成两个部分，其中一部分记录关键字均比另一部分记录的关键字小，则可以分别对这两部分关键字继续排序，以达到整个序列有序的目的。 * 时间复杂度：O(nlogn),最坏的情况下为O(n^2)         空间复杂度：O(1)         稳定性:不稳定 * */function sortGuo5(arr, leftIndex, rightIndex) {  if (leftIndex < rightIndex) {    var index = quickSortGuo(arr, leftIndex, rightIndex); //进行一趟排序    sortGuo5(arr, leftIndex, index);    sortGuo5(arr, index + 1, rightIndex);  }  return arr;}function quickSortGuo(arr, leftIndex, rightIndex) {  var base = arr[leftIndex];  var tem;  while (leftIndex < rightIndex) {    while (leftIndex < rightIndex && arr[rightIndex] >= base) {      rightIndex--;    }    tem = arr[rightIndex];    arr[rightIndex] = arr[leftIndex];    arr[leftIndex] = tem;    while (leftIndex < rightIndex && arr[leftIndex] <= base) {      leftIndex++;    }    tem = arr[rightIndex];    arr[rightIndex] = arr[leftIndex];    arr[leftIndex] = tem;  }  return leftIndex;}var arr5 = [311, 32, 32, 3, 346, 457, 56, 7, 56, 8, 679, 78];alert(sortGuo5(arr5, 0, arr5.length - 1));