【深入Java基础】排序算法（一）

1.冒泡排序

基本思想（升序）：属于交换排序。依次比较前一个数和后一个数的大小，若后一个数小于前一个数，则交换位置，否则不交换，一趟下来，最大的数就被交换到了尾部。

3 2 1 5 4

2 1 3 4 5

1 2 3 4 5

最差时间时间复杂度：O(n²)

平均时间时间复杂度：O(n²)

稳定性：稳定

public void bubbleSort(int[] array){  
        for(int i=0;i<array.length;i++){  
            for(int j=1;j<array.length-i;j++){  
                if(array[j]<array[j-1]){  
                    swap(array,j,j-1);  
                }  
            }  
        }  
    }  
    private void swap(int[] array,int i,int j){  
        int temp = array[i];  
        array[i] = array[j];  
        array[j] = temp;  
    }

优化：设置标记，当一次循环没有元素交换时，提前结束循环。

public void bubbleSort(int[] array){  
        boolean flag = false;  
        for(int i=0;i<array.length;i++){  
            for(int j=1;j<array.length-i;j++){  
                if(array[j]<array[j-1]){  
                    swap(array,j,j-1);  
                    flag = true;  
                }  
                if(!flag)  
                    break;  
            }  
        }  
    }

适用场景：数据基本有序时。

2.选择排序

基本思想（升序）：每次循环选择最小的，依次放在有序部分的后边。

3 2 1 5 4

1 2 3 5 4

1 2 3 4 5

最差时间复杂度：O(n²)

平均时间复杂度：O(n²)

稳定性：不稳定

public void selectionSort(int[] array){  
      for(int i=0;i<array.length;i++){  
          int minIndex = i;  
          for(int j=i+1;j<array.length;j++){  
              if(array[j]<array[minIndex]){  
                  minIndex = j;  
              }  
          }  
          if(i!=minIndex)  
              swap(array, i, minIndex);  
      }  
  }  

  private void swap(int[] array,int i,int j){  
      int temp = array[i];  
      array[i] = array[j];  
      array[j] = temp;  
  }

使用场景：数据量较小时

3.插入排序

基本思想（升序）：假设前n-1个元素已经有序，选择第n个元素插入到前n-1个元素中的正确位置，并使插入位置后的元素依次右移。

3 2 1 5 4

3 2 1 4 5

其中红色左边为已经排序好的，右边为待排序的，红色为当前待插入的元素。

最差时间复杂度：O(n²)

平均时间复杂度：O(n²)

稳定性：稳定

public void insertSort(int[] array) {  
        for (int i = 1; i < array.length; i++) {  
            int temp = array[i];  
            int j;  
            for (j = i; j > 0 && temp < array[j - 1]; j--) {  
                array[j] = array[j - 1];  
            }  
            array[j] = temp;  
        }  
    }

使用场景：数据基本有序时

4.Shell排序

基本思想：Shell排序属于插入排序。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

public void shellSort(int[] array) {  
        int d,i,j;  
        for(d = array.length/2;d>0;d/=2){  
            for(i=d;i<array.length;i++){  
                for(j=i-d;j>=0&&array[j]>array[j+d];j-=d){  
                    swap(array,j,j+d);  
                }  
            }  
        }  

    }

适用场景：数据基本有序时

5.快速排序

基本思想（升序）：属于交换排序。

先从数列中取出一个数作为基准数
分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
再对左右区间重复第二步，直到各区间只有一个数

3 2 1 5 4

2 1 3 5 4

1 2 3 4 5

最差时间复杂度：O(n²)

平均时间复杂度：O(nlgn)

public void quicklySort(int[] array){  
     quicklySort(array,0,array.length-1);  
 }  

 private void quicklySort(int array[],int left,int right){  
     if(left>right)  
         return;  

     int temp = array[left];  
     int i=left,j=right;  

     while (i<j){  
         System.out.println("i="+i+",j="+j);  
         while (array[j]>temp&&i<j)  
             j--;  
         while (array[i]<temp&&i<j)  
             i++;  
         if(i<j)  
             swap(array,i,j);  
             System.out.println(Arrays.toString(array));  
     }  
     quicklySort(array,left,i-1);  
     quicklySort(array,j+1,right);  
 }

适用场景：快排的效率一般比较好，适用于大量数据的排序