各种排序算法

本文介绍: 冒泡排序是一种简单的排序算法，它不断地重复遍历数组，每次与其相邻的数进行比较，如果他们的顺序错误就交换，直到数组只剩下一个元素的时候，说明该数组已经排好序，之所以成为冒泡排序，是因为越小的元素会经由交换慢慢“浮”到数列的前面。选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。①时间复杂度：最好情况：O（n*logn）；②最坏情况下：时间复杂度为O（n^2）①最好情况：时间复杂度为O（n）

1.Arrays.sort—默认升序

//降序排序
Integer a[] = {6,9,9};
Arrays.sort(a, Collections.reverseOrder());
for (int i = 0; i < a.length; i++) {
    System.out.print(a[i]);
}

2.直接插入排序

① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤

//降序排序
int temp = 0;
int a[] = {9,3,6,2,8,1,3} ;
if (a.length == 1){
     System.out.println(a[0]);
} else {
     for (int i = 1; i < a.length; i++) {
          for (int j = 0; j < i ; j ++){
             if (a[i] > a[j]){
                  temp = a[j];
                  a[j] = a[i];
                  a[i] = temp;
              }
           }
      }
 }
 for (int i = 0; i < a.length; i++) {
     System.out.print(a[i]);
 }

性能分析：

        ①平均时间复杂度：O(N^2)
        ②最差时间复杂度：O(N^2)
        ③空间复杂度：O(1)
        ④稳定性：稳定

3.希尔排序

将要排序的序列按照步长gap进行分组，先在这几组内进行插入排序，之后再进行整体的插入排序，gap步长的选择是希尔排序最重要的部分，要保证最后一次排序的步长为1，这样就会保证整个数组将会被排序，并且步长必须小于数组长度。

public void shellSort() {
   //gap是为了分组；
   int[] array = {9,3,6,2,8,1,3};
   int gap = array.length;
   while (gap > 1) {
      //下一次的组数是上一次的一半；
      gap /= 2;
      shell(array, gap);
   }
   for (int i = 0; i < array.length; i++) {
      System.out.print(array[i]);
   }
}
public void shell(int[] array, int gap) {
   int temp = 0,b = gap;
   for (int i = 0; i <= b; i++) {
       if (array[gap] > array[i]){
           temp = array[i];
           array[i] = array[gap];
           array[gap] = temp;
        }
        if (gap < array.length){
            ++gap;
         }
     }
}

性能分析：

        ①最好情况：时间复杂度为O（n）
        ②最坏情况下：时间复杂度为O（n^2）
        ③空间复杂度为：O(1)
        ④稳定性：不稳定

4.选择排序

选择排序原理即是，遍历元素找到一个最小（或最大）的元素，把它放在第一个位置，然后再在剩余元素中找到最小（或最大）的元素，把它放在第二个位置，依次下去，完成排序。、

//降序排序
int temp = 0;
int a[] = {6,9,9} ;
for (int i = 0; i < a.length; i++) {
   for (int j = i + 1; j < a.length ; j ++){
        if (a[i] < a[j]){
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
         }
    }
 }
 for (int i = 0; i < a.length; i++) {
    System.out.print(a[i]);
 }

性能分析：

        ①时间复杂度：O（n^2）；
        ②空间复杂度：O（1）；
        ③稳定性：不稳定；

5.堆排序

从小到大排序建大堆，从大到小排序建小堆
把堆顶的元素和当前堆的最后一个元素交换
堆的元素个数减一
从根节点向下调整

性能分析：

        ①最好情况下时间复杂度为：O(nlogn)
        ②最坏情况下时间复杂度为：O(nlogn)
        ③空间复杂度为：O(1)
        ④稳定性：不稳定

6.冒泡排序

冒泡排序是一种简单的排序算法，它不断地重复遍历数组，每次与其相邻的数进行比较，如果他们的顺序错误就交换，直到数组只剩下一个元素的时候，说明该数组已经排好序，之所以成为冒泡排序，是因为越小的元素会经由交换慢慢“浮”到数列的前面。

//降序排序
int temp = 0;
int a[] = {8,3,9,4,5,2,6,8} ;
if (a.length == 1){
    System.out.println(a[0]);
} else {
    //每一趟都会排出一个最大/最小值，所以需要排序a.length - 1轮
    for (int z = 0; z < a.length - 1; z++) {
        int j = 1;
        for (int i = 0; i < a.length -1;i++) {
            if (a[i] < a[j]){
               temp = a[j];
               a[j] = a[i];
               a[i] = temp;
             }
             j++;
         }
     }
}
for (int i = 0; i < a.length; i++) {
   System.out.print(a[i]);
}

性能分析：

        ①最坏情况时间复杂度为：Ｏ（ｎ＾２）。
        ②平均情况时间复杂度为：Ｏ（ｎ＾２）。
        ③需要额外空间：Ｏ（１）。
        ④稳定性：稳定。

7.快速排序

这里是引用选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。