各种排序算法_代码007(未授权)

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

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

//降序排序
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]);
 }

//降序排序
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]);
}