Java完成直接拔出排序和折半拔出排序算法示例。本站提示廣大學習愛好者：（Java完成直接拔出排序和折半拔出排序算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成直接拔出排序和折半拔出排序算法示例正文
直接拔出排序
1 排序思惟：
將待排序的記載Ri拔出到曾經排好序的記載R1，R2，……，R（N-1）中。
關於一個隨機序列而言，就是從第二個元素開端，順次將這個元素拔出到它之前的元素中的響應地位。它之前的元素曾經排好序。
第1次排序：將第2個元素拔出到前邊的有序列表（此時前邊只要一個元素，固然是有序的），以後，這個序列的前2個元素就是有序的了。
第2次排序：將第3個元素拔出到前邊長度為2的有序列表，使得前2個元素是有序的。
以此類推，直到將第N個元素拔出到後面長度為（N-1）的有序列表中。
2 算法完成：
// 直接拔出排序
void straight_insert_sort(int num[], int len){
int i,j,key;
for(j=1;j<len;j++){
key=num[j];
i=j-1;
while(i>=0&&num[i]>key){
num[i+1]=num[i];
i--;
}
num[i+1]=key;
}
}
3 機能剖析：
3.1 空間龐雜度：如上代碼，應用了一個幫助單位key，空間龐雜度為O(1)
3.2 時光龐雜度：
3.2.1 最好情形：待排序記載曾經是有序的，則一趟排序，症結字比擬1次，記載挪動2次。則全部進程
比擬次數為
記載挪動次數為
時光龐雜度O(n)
3.2.2 最壞情形：待排序記載曾經是逆序的，則一趟排序，症結字比擬次數i次（從i-1到0），記載挪動（i+2）次。全部進程
比擬次數為
記載挪動次數為
時光龐雜度O(n^2)
3.2.3 均勻時光龐雜度：O(n^2)
3.3 穩固性：穩固
折半拔出排序
1 排序思惟：
直接排序的基本上，將待排序的記載Ri拔出到曾經排好序的記載R1，R2，……，R（N-1）中，因為記載R1，R2，……，R（N-1）曾經排好序，所以在查找拔出地位時可采取“折半查找”。
2 算法完成：
// 折半拔出排序
void binary_insert_sort(int num[], int len){
int i,j,key,low,high,mid;
for(i=1;i<len;i++){
key=num[i];
low=0;
high=i-1;
mid=(low+high)/2;
// 尋覓拔出點，終究拔出點在low
while(low<=high){
if(key<num[mid])
high=mid-1;
else
low=mid+1;
mid=(low+high)/2;
}
// 挪動記載
for(j=i;j>low;j--){
num[j]=num[j-1];
}
// 拔出記載
num[low]=key;
}
}
3 機能剖析：
3.1 空間龐雜度：如上代碼，應用了一個幫助單位key，空間龐雜度為O(1)
3.2 時光龐雜度：固然折半查找削減了記載比擬次數，但沒有削減挪動次數，是以時光龐雜度同直接查找算法。
3.2.1 最好情形：時光龐雜度O(n)
3.2.2 最壞情形：時光龐雜度O(n^2)
3.2.3 均勻時光龐雜度：O(n^2)
3.3 穩固性：穩固
