package com.wang.sort;
/**
* 插入排序：每次將一個(gè)待排序的記錄棵里，按其關(guān)鍵之大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置裸卫，知道全部記錄插入完畢
*
* @author wxe
* @since 0.0.1
*/
public class InsertSort {
public static int count = 0;
public static void main(String[] args){
int[] array = {2,3,7,3,9,4,5};
insertSort(array, array.length);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ",");
}
System.out.println();
System.out.println("總次數(shù)："+count);
}
public static void insertSort(int[] array,int length){
for(int i = 1;i<length;i++){
for (int j = i-1; j >=0 && array[j]>array[j+1]; j--) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
count++;
}
}
}
}
比較相同數(shù)據(jù)，只需要5次排序即可揪惦，所以說(shuō)插入排序還是優(yōu)于冒泡排序的奕坟。
簡(jiǎn)單插入排序在最好情況下祥款，需要比較n-1次，無(wú)需交換元素执赡，時(shí)間復(fù)雜度為O(n);在最壞情況下镰踏，時(shí)間復(fù)雜度依然為O(n2)。
