排序算法

常见的几种排序算法的java描述

冒泡排序

public static void bubbleSort(int[] arr){
  int len = arr.length;
  for(int i=0; i<len; i++){
      for(int j=0; j<len-1-i; j++){
          if(arr[j] > arr[j+1]){     // 相信元素比大小
              int temp = arr[j+1];   // 元素位置交换，从小到大排列
              arr[j+1] = arr[j];
              arr[j] = temp;
          }
      }
  }
}

选择排序

public static void selectionSort(int[] arr){
  int len = arr.length;
  int minIndex, temp;
  for(int i=0; i<len; i++){
      minIndex = I;
      for(int j=i+1; j<len; j++){
          if(arr[j] < arr[minIndex]){ // 寻找最小的数
              minIndex = j;         // 保存最小数的索引号
          }
      }
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
  }
}

不稳定例子：5、8、5、2、6

第一遍选择 第一个位置的5会和2交换，从而第一个5会到第二个5后面了

插入排序

  public static void insertSort(int[] arr){
      for(int p =1;p<arr.length;p++){
          int temp = arr[p];
          int j;
          for(j =p;j>0&&temp<arr[j-1];j--){
              arr[j] = arr[j-1];
          }
          if(j!=p){
              arr[j] = temp;
          }

      }
  }

快速排序

快速排序的基本思想：挖坑填数+分治法

• 1．先从数列中取出一个数作为基准数。

• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

• 3．再对左右区间重复第二步，直到各区间只有一个数

void quickSort(int a[], int lo, int hi){
  int i = lo, j = hi;
  int temp;
  if(i < j){
      temp = a[I];
      while (i != j)
      {
          while(j > i && a[j] >= temp)-- j;
          a[i] = a[j];
          while(i < j && a[i] < temp)++ I;
          a[j] = a[I];
      }
      a[i] = temp;
      quickSort(a, lo, i - 1);
      quickSort(a, i + 1, hi);
  }
}

希尔排序

第一个突破O(n2)的排序算法

希尔排序也是一种插入排序,希尔排序的核心在于间隔序列的设定,分组后进行插入排序

(图片来源于网络)

public static void shellSort(int[] a){
  for(int gap = a.length/2;gap>0;gap/=2){
      for(int i = gap;i<a.length;i++){
          int temp = a[I];
          int j;
          for(j = i;j-gap>=0&&temp<a[j-gap];j = j-gap){
              a[j] = a[j-gap];
          }
          a[j]=temp;
      }
  }
}