歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

排序總結之插入式排序

算法概述:

插入排序(Insertion Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反復把已排序元素逐步向後挪位,為最新元素提供插入空間。

插入排序主要分為三種,即直接插入,二分插入(利用二分法來減少比較次數),希爾排序(又稱縮小增量排序)

插入的主要步驟:

1,從第一個元素開始,該元素可以認為已經被排序
2,取出下一個元素,在已經排序的元素序列中從後向前掃描
3,如果該元素(已排序)大於新元素,將該元素移到下一位置
4,重復步驟3,直到找到已排序的元素小於或者等於新元素的位置
5,將新元素插入到該位置後
6,重復步驟2~5

復雜度分析:

直接插入復雜度:

最差時間復雜度 最優時間復雜度 平均時間復雜度 最差空間復雜度 總共 ,需要輔助空間

二分插入復雜度:

 

 

插入每個記錄需要O(log i)比較,最多移動i+1次,最少2次
最佳情況O(nlog n),最差和平均情況O(n^2)。

希爾排序復雜度:

最差時間復雜度 根據步長串行的不同而不同。 已知最好的:  最優時間復雜度 O(n) 平均時間復雜度 根據步長串行的不同而不同。 最差空間復雜度 O(n)

代碼示例:

package com.louxue.sort;

import java.util.Arrays;
/**
 * 插入排序
 * @author louxuezheng 2014年3月10日
 */
public class InsertSort {
 public static void main(String... args) {
  int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62,
    99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
  // new InsertSort().insertSort(a);// 直接插入排序
  // new InsertSort().shellSort(a);
  // new InsertSort().shellSort2(a);
  new InsertSort().binaryInsertSort(a);
  System.out.println(Arrays.toString(a));
 }

 /**
  * 直接插入排序是穩定的排序
  * 基本思想:在要排序的一組數中,假設前面(n-1)[n>=2] 個數已經是排 好順序的,
  * 現在要把第n個數插到前面的有序數中,使得這n個數 也是排好順序的。
  * 如此反復循環,直到全部排好順序。
  * @param a
  */
 private void insertSort(int[] a) {
  int temp = 0;
  for(int i=1;i<a.length;i++){
   int j=i-1;
   temp = a[i];// 要被插入的第i個數,這個數與前面的排好序的數進行比較。比它大的整體都向後移動
   while (j >= 0 && temp < a[j]) {
    a[j + 1] = a[j];
    j--;
   }
   a[j + 1] = temp;
  }
 }

 /**
  * shell排序是不穩定的。
  * 基本思想:算法先將要排序的一組數按某個增量d(n/2,n為要排序數的個數)分成若干組,
  * 每組中記錄的下標相差d. 對每組中全部元素進行直接插入排序,然後再用一個較小的增量
  * (d/2)對它進行分組,在每組中再進行直接插入排序。當增量減到1時,進行直接插入排序後,排序完成。
  *
  * @param a
  */
 private void shellSort(int[] a) {
  double d1 = a.length;
  int temp = 0;
  while (true) {
   d1 = Math.ceil(d1 / 2);// 向上取整計算,它返回的是大於或等於函數參數,並且與之最接近的整數。
   int d = (int) d1;
   for (int x = 0; x < d; x++) {
    for (int i = x + d; i < a.length; i += d) {
     int j = i - d;
     temp = a[i];
     for (; j >= 0 && temp < a[j]; j -= d) {
      a[j + d] = a[j];
     }
     a[j + d] = temp;
    }
   }
   if (d == 1)
    break;
  }
 }

 /**
  * Knuth 提出的d=[d/3]+1,下取整。
  *
  * @param a
  */
 private void shellSort2(int[] a) {
  int d = a.length;
  int temp = 0;
  do {
   d=d/3+1;
   for (int x = 0; x < d; x++) {
    for (int i = x + d; i < a.length; i += d) {
     int j = i - d;
     temp = a[i];
     for (; j >= 0 && temp < a[j]; j -= d) {
      a[j + d] = a[j];
     }
     a[j + d] = temp;
    }
   }
  } while (d > 1);
 }
 /**
  * 折半插入排序是穩定的排序
  * 又稱為二分插入排序,基本思想:設在數組中前i-1個元素是已經排好序的,
  * 在插入a[i]時,利用二分搜索的方法找到a[i]的位置插入。
  * @param a
  */
 private void binaryInsertSort(int[] a) {
  int temp = 0;
  int i, low, high, middle, k;
  for (i = 1; i < a.length; i++) {
   temp = a[i];
   low = 0;
   high = i - 1;
   while (low <= high) {
    middle = (low + high) / 2;
    if (temp < a[middle]) {
     high = middle - 1;
    } else
     low = middle + 1;
   }
   for (k = i - 1; k >= low; k--)
    a[k + 1] = a[k];// 成塊移動空出插入位置
   a[low] = temp;
  }
 }
}

Copyright © Linux教程網 All Rights Reserved