十大经典排序算法

冒泡排序

  1. 从第一个元素开始，比较相邻的两个元素，如果第一个比第二个大，交换两者；
  2. 然后再比较第二个元素和第三个元素，如果3>2继续交换；
  3. 这样进行一轮之后，最大的元素一定会冒泡到最后；

  4. 对剩下的元素重复1-3；

    1. int[] array = {2,3,5,1,4,6,8,7,9};
    2. for(int i=0;i<9-1;i++)
    3. {
    4.  for(int j=0;j<9-1-i;j++)
    5.  {
    6.      if(array[j]>array[j+1])
    7.      {
    8.          int temp = array[i+1];
    9.          array[j+1] = array[j];
    10.          array[j] = temp;
    11.      }
    12.  }
    13. }

    冒泡排序的时间复杂度为O(n^2)；可以将冒泡排序理解为两个for的嵌套；冒泡排序的空间复杂度为O(1)；额外占用的空间仅仅是一个temp；

    选择排序

  5. 选定第一个元素，然后遍历剩下的元素，挨个和这个元素比较，如果找到了比第一个元素更小的，记录下来，再用这个更小的元素向后遍历&比较，寻找更小的；如果找到了，替换被记录的元素，直到遍历结束；

  6. 交换第一个元素和剩下元素中最小的元素的位置；

  7. 重复1-2；

    1. int[] array = {2,3,5,1,4,6,8,7,9};
    2. for(int i=0;i<9-1;i++)
    3. {
    4.  int index=i;
    5.  for(int j=i+1;j<9;j++)
    6.  {
    7.      if(array[j]<array[index])
    8.      {
    9.          index=j;
    10.      }
    11.  }
    12.  int temp = array[index];
    13.  array[index] = array[i];
    14.  array[i] = temp;
    15. }

    选择排序的时间复杂度为O(n^2)，而且十分稳定，从这点上看，其实选择排序甚至还不如冒泡排序（冒泡排序消耗的时间可能更少….），空间复杂度同样为O(1)，无需占用额外的空间；

    插入排序

  8. 使用第二个元素和第一个元素比较，如果2>1，无事发生，如果2<1，那么将第二个元素插入第一个元素之前；（也就是让1和2交换，这里使用“插入”来描述，主要是为了符合插入排序的特点）；

  9. 使用第三个元素和第二个元素比较，如果3>2，无事发生，如果3<2，让原先的2向后移动一个index成为3，然后再让原先的3和原先的1进行比较，如果3<1的话，让1向后移动一个index，原先的3成为了1；

  10. 依次向后进行重复步骤1

    1. int[] array = {2,3,5,1,4,6,8,7,9};
    2. for(int i=1;i<9;i++)
    3. {
    4.  //记录当前的array【i】
    5.  int temp = array[i];  
    6.  for(int j=i-1;j>0;j--)
    7.  {
    8.      if(temp<array[j])
    9.      {
    10.          //向后移动;
    11.          array[j+1] = array[j];
    12.      }
    13.      else
    14.      {
    15.          array[j] = temp;
    16.          break;
    17.      }
    18.  }
    19. }

    插入排序的平均时间复杂度为O(n^2)；本质上还是两个循环的嵌套

    Shell sort 希尔排序

    希尔排序被发明与1959年，是第一个时间复杂度小于O(n^2)的排序方式；希尔排序的操作引入了步长的概念；例如：

  11. {4,5,7,2}的下标分别为0123，此时如果设定步长为2，那么在第一轮排序中，下标为0的元素和下标为（0+2）的元素进行比较，4<7，不用做额外的动作；

  12. 下标为1的元素和下表为（1+2）的元素进行比较，5>2，此时，交换两者；数组变为{4,2,7,5}；
  13. 然后缩小步长；（新步长必须比old小，但是一定得是整数）；原先步长为2，现在为2/2=1；
  14. 这时候第希尔排序就退化成了插入排序；

实际上shell Sort是分组进行的插入排序…对于奇数长度的数组，只能将最后余下的内容放到步长=1的时候处理； 

  1. int[] array = {2,3,5,1,4,6,8,7,9};
  2. function shellSort(arr) {
  3.     varlen = arr.length;
  4.     for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
  5.         for(vari = gap; i < len; i++) {
  6.             varj = i;
  7.             varcurrent = arr[i];
  8.             while(j - gap >= 0 && current < arr[j - gap]) {
  9.                  arr[j] = arr[j - gap];
  10.                  j = j - gap;
  11.             }
  12.             arr[j] = current;
  13.         }
  14.     }
  15.     returnarr;
  16. }

希尔排序的时间复杂度在O(n^1.3)-O(n^2)之间

归并排序

  1. 将长度为n的数组分为两半，各自进行归并；
  2. 持续进行将数组分半的操作，直到数组被分为，n/2个长度为2的数组（仅仅包含两个内容）
  3. 对第一个子数组进行排序，此时相对简单…只需要对两个元素进行排序即可；
  4. 对第二个长度为2的子数组排序，此时获得了两个长度2的有序素组
  5. 对这两个数组进行归并，排序，生成长度为4的有序数组
  6. 对第三个和第四个数组重复3-5步，直到将所有的长度为2的数组两两归并成长度为4的数组
  7. 完成之后，将获得n/4个数组，重复3-7步，不过此时无需再对长度为4的数组排序，直接将长度为4的两个数组归并为长度为8的两个数组即可；
  8. 持续归并，直到获取到完整的数组；

对于奇数长度的数组，例如{1，2，3，4，5}，会分成{1,2}和{3，4}和{5};此时对{12}和{34}归并，然后再进行{1234}和{5}的归并；

function mergeSort(arr) {
    varlen = arr.length;
    if(len < 2) {
        returnarr;
    }
    varmiddle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    returnmerge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    varresult = [];

    while(left.length>0 && right.length>0) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else{
            result.push(right.shift());
        }
    }

    while(left.length)
        result.push(left.shift());

    while(right.length)
        result.push(right.shift());

    returnresult;
}

归并排序的时间复杂度相对较低，是固定的O(nlong)；代价是需要额外的空间；

快速排序

  1. 从数列中取出一个元素作为key；
  2. 将比key小的元素放到key的右侧，比key大的元素放到key的右侧；
  3. 对左右两个部分重复1-2；直到各个区间只有一个数； ```c void QSort(int a[],int length,int r) { if(length>r)
     return;

} ```