常用排序算法（一）-java实现

排序算法总结

1.十大经典算法及性能

2.具体排序算法

1.冒泡排序

• 循环过程中比较相邻两个数大小，通过交换正确排位，循环整个数组即可完成排序

• 图片演示

• 代码实现Java

  //冒泡排序
  public static Integer[] Bubble(Integer[] array){
          boolean ranked = false;
          for (int i = 0; i < array.length; i++) {
              for(int j=0;j<array.length-i-1;j++){
                  if(array[j]>array[j+1]){
                      int c = array[j];
                      array[j] = array[j+1];
                      array[j+1] = c;
                      ranked = true;
                  }
              }
              if(!ranked){
                  break;
              }
          }
          return array;
      }
  

2.选择排序

• 选择最大的排到最右边或选择最小的排到最左边

• 图片演示

• 代码实现(Java)

  public static int[] SelectSort( int[] array){
          for (int i = 0; i < array.length; i++) {
              int min = i;
              for(int j = i+1; j < array.length; j++){
                  if(array[j]<min){
                      min = j;
                  }
              }
              int c = array[i];
              array[i] = array[min];
              array[min] = c;
          }
          return array;
      }
  

3.插入排序

• 把左边当做已完成序列，右边作为未完成排序，遍历右边插入到左边已完成序列中

• 图片演示

• 代码实现

  public  static int[] insertionSort(int[] array){
          for(int i = 1; i < array.length; i++){
              int complete = i-1;
              int current = array[i];
              while(complete >=0 && array[complete]>current){
                  array[complete+1] = array[complete];
                  complete--;
              }
              array[complete+1] = current;
          }
          return array;
      }
  

4.希尔排序

• 希尔排序是插入排序的改进算法，但它是不稳定算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。参考：https://www.cnblogs.com/chengxiao/p/6104371.html

• 图片演示

• 代码实现

//希尔排序
public static int[] shellSort(int[] array){
        int current;
        for(int step=array.length/2;step>=1;step/=2){
            for(int i = step;i<array.length;i++){
                current = array[i];
                int j = i-step;
                while(j>=0&&array[j]>=current){
                    array[j+step] = array[j];
                    j -= step;
                }
                array[j+step] = current;
            }
        }
        return array;
    }

5.归并排序

• 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

• 两种实现方式

  • 自上而下的递归
  • 自下而上的迭代

• 图片演示

• 代码实现(java)

  public int[] sort(int[] sourceArray) throws Exception {
          // 对 arr 进行拷贝，不改变参数内容
          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  
          if (arr.length < 2) {
              return arr;
          }
          int middle = (int) Math.floor(arr.length / 2);
  
          int[] left = Arrays.copyOfRange(arr, 0, middle);
          int[] right = Arrays.copyOfRange(arr, middle, arr.length);
  
          return merge(sort(left), sort(right));
      }
  
      protected int[] merge(int[] left, int[] right) {
          int[] result = new int[left.length + right.length];
          int i = 0;
          while (left.length > 0 && right.length > 0) {
              if (left[0] <= right[0]) {
                  result[i++] = left[0];
                  left = Arrays.copyOfRange(left, 1, left.length);
              } else {
                  result[i++] = right[0];
                  right = Arrays.copyOfRange(right, 1, right.length);
              }
          }
  
          while (left.length > 0) {
              result[i++] = left[0];
              left = Arrays.copyOfRange(left, 1, left.length);
          }
  
          while (right.length > 0) {
              result[i++] = right[0];
              right = Arrays.copyOfRange(right, 1, right.length);
          }
  
          return result;
      }