排序演算法二分法

⑴ java 二分法排序

public class Lookup {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
/**
* 二分法查找
*/
int a[]={23,45,98,100,110,120,140};
int search=120;//記錄要查找的元素
int lower=0;//記錄第一個元素
int temp=a.length-1 ;
int index=-1;
while(lower<=temp){
index = (lower+temp)/2;//記錄中間元素，用兩邊之和除2.
int currentValue=a[index];
if(currentValue==search){//如果得到的數與要查找的數相等則break退出;
break;
}else if(currentValue<search){//如果得到的數要小於查找的數、就用下標加1;否則減一
lower=index+1;
}else{
temp = index-1;
}
}
if(lower<=temp){
System.out.println(search+"在數組中第："+(index+1)+"位");
}else{
System.out.println("裡面沒有這個元素");
}
}
}

⑵ 「二分法插入排序」、「快速排序」、「歸並排序」和「堆排序」的時間復雜度分別是多少

排序演算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在計算機科學所使用的排序演算法通常被分類為： 計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。 記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。 一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。 當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有： (3, 1) (3, 7) (4, 1) (5, 6) (維持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。 排列演算法列表 在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n);
需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2) 二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2) Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n)
如果使用最佳的現在版本 Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n) Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n)
期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序 Introsort — O(n log n) Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence） 不實用的排序演算法 Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。 Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體 Bead sort — O(n) or O(√n), 但需要特別的硬體 Pancake sorting — O(n), 但需要特別的硬體 排序的演算法 排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。 插入排序 冒泡排序 選擇排序 快速排序 堆排序 歸並排序 基數排序 希爾排序 插入排序 插入排序是這樣實現的： 首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。 從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。 重復2號步驟，直至原數列為空。 插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。 冒泡排序 冒泡排序是這樣實現的： 首先將所有待排序的數字放入工作列表中。 從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。 重復2號步驟，直至再也不能交換。 冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。 選擇排序 選擇排序是這樣實現的： 設數組內存放了n個待排數字，數組下標從1開始，到n結束。 i=1 從數組的第i個元素開始到第n個元素，尋找最小的元素。 將上一步找到的最小元素和第i位元素交換。 如果i=n－1演算法結束，否則回到第3步 選擇排序的平均時間復雜度也是O(n²)的。 快速排序 現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。 堆排序 堆排序與前面的演算法都不同，它是這樣的： 首先新建一個空列表，作用與插入排序中的"有序列表"相同。 找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。 重復2號步驟，直至原數列為空。 堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。 看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。 平均時間復雜度 插入排序 O(n2) 冒泡排序 O(n2) 選擇排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 歸並排序 O(n log n) 基數排序 O(n) 希爾排序 O(n1.25)

⑶ 順序表的排序，二分法查找的c語言程序

#include<stdio.h>
int fun(int a[],int n,int key)
{i
nt low,mid,high;//low、mid、high是三個索引分別指向數組的下標low=0;//low指向數組a[]的第一個元素，即下表為0的元素
high=n-1;//lhigh指向數組a[]的最一個元素，即下表為n-1的元素，n為數組的長度
while(low<=high)//循環終止條件是low>high的時候
{
mid=(low+high)/2;//所謂二分查找就在這里，每次都讓mid指向數組下標等於low和high之和的一半的元素i
f(key<a[mid])//如果a【mid】大於要查找的元素，說明要查找的元素在low和mid之間，這是需要把high重新置為mid-1
(high=mid-1);//這里應該是{}，不能使（）吧
else if(key>a[mid])//這里同理，如果a【mid】小於要查找的元素，說明要查找的元素在mid和high之間，這是需要把low重新置為mid+1
(low=mid+1);
else
return mid;//剩下的就是相等的情況，直接返回mid就是查找到的結果
}
return -1;//執行到這一步就說明，low>high，沒有找到要查找的元素，返回-1表示沒有結果
}
main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int a,b,c;
b=4;
c=fun(a,10,b);
if(c==1)
printf("not found");
else
printf("psition %d\n",c);
}

⑷ 求二分法排序的c語言演算法

#include <stdio.h>
int a[10]={21,56,43,12,3,99,56,23,2,12};
main()
{
int i,j,k,low,high,mid,t;
for(i=k=1;i<sizeof a/sizeof a[0];i++)//起始認為第一個元素是有序的,high=low=k-1=0,所以k=1,
{
low=0;
high=k-1;
while(low<=high)////折半查找時，low與high相遇，則找到插入位置
{
mid=(low+high)/2;
if(a[mid]>=a[i])high=mid-1;///////元素比mid小，因此在low到mid-1范圍內搜索位置
else low=mid+1;
}
if(high<i|| a[low]!=a[i]) ///////////
{
t=a[i];
for(j=k-1;j>=low;j--) //////插入位置是low，所以low到high=k-1范圍內的元素都要向後移動
a[j+1]=a[j];
a[low]=t; //////////////low被賦值為已經被覆蓋掉的a[i]
k++;
}
}
for(j=0;j<k;j++)
printf("%4d",a[j]);
printf("\n");
}

自己修改一下，把注釋去了，能運行，剛剛運行過了。

⑸ java 二分法 排序

二分排序就是用先用二分查找法來查某一個元素，然後再用別的排序演算法來進行排序。

package insert;

public class InsArrayApp {
public static void main(String[] args) {
int size = 100;
InsArray arr = new InsArray(size);

arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(7);
arr.insert(6);
arr.insert(10);
arr.insert(9);
arr.insert(8);
arr.insert(5);
arr.insert(4);
arr.insert(3);
arr.insert(2);
arr.insert(1);

arr.display();

// arr.insertSort();

// arr.display();

// System.out.println(arr.median());

// arr.noDups();

arr.noDups2();
arr.display();
}
}

class InsArray {
private int[] a;
private int nElems;

public InsArray(int size) {
a = new int[size];
nElems = 0;
}

public void insert(int value) {
a[nElems] = value;
nElems++;
}

public void display() {
for (int i = 0; i < nElems; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}

public void insertSort() {
int out, in;
int = 0;
int compare = 0;
/* for(out = 1;out<nElems;out++){
int tmp = a[out];
in = out;
while(in>0&&a[in-1]>=tmp){
a[in] = a[in-1];
--in;
}
a[in] = tmp;
}*/
for(out = 1;out<nElems;out++){
int tmp = a[out];
in = out;
while(in>0){
if(a[in-1]>=tmp){
a[in] = a[in-1];
--in;
++;
++compare;}
else{
break;
}
}
++compare;
a[in] = tmp;
}
System.out.println(":" + + "compare:" + compare);
}

public int median(){
insertSort();
int m = nElems/2;
return a[m];
}

public void noDups(){
insertSort();
/*
InsArray tmp = new InsArray(nElems);
for(int i = 0;i<nElems;i++){
for(int j = i+1;j<nElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
if(a[i]!=-1)
tmp.insert(a[i]);
}
*/
InsArray tmp = new InsArray(nElems);
int i;
for(int j = 0;j<this.nElems;j++){
/*if(tmp.nElems==tmp.find(this.a[j])) //binary find
tmp.insert(this.a[j]);
else
continue;*/
for( i = 0; i < tmp.nElems; i++) { // for each element
if(tmp.a[i]==this.a[j]) // found searchKey?
break;
}
if(i==tmp.nElems) // no
tmp.insert(this.a[j]);
}
this.a = tmp.a;
this.nElems = tmp.nElems;
}

public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems-1;
int curIn;

while(true) {
curIn = (lowerBound + upperBound)/2;
if(a[curIn]==searchKey)
return curIn;
else if(lowerBound>upperBound)
return nElems;
else {
if(a[curIn]>searchKey)
upperBound = curIn-1;
else
lowerBound = curIn+1;
}
}
}

public void noDups2(){
insertSort();
for(int i = 0;i<nElems;i++){
for(int j = i+1;j<nElems;j++)
if(a[i] == a[j]){
a[j] = -1;
}
}
display();
int index = 0;
for(int i=0;i<nElems;i++){
if(a[i]!=-1){
index++;
}else{
for(int j=index+1;j<nElems;j++){
if(a[j]!=-1){
a[index] = a[j];
a[j]=-1;
index++;
break;
}
}
}
}
nElems = index;

}
}

上面的代碼，是我以前敲的，有個find()方法是二分查找，然後再用插入排序去進行排序。

⑹ 快速排序和二分法排序哪個快

選擇排序、快速排序、希爾排序、堆排序不是穩定的排序演算法，而冒泡排序、插入排序、歸並排序和基數排序是穩定的排序演算法

⑺ 在最差情況下復雜度仍然是O的排序演算法是什麼演算法

二分法二分法的基本思想如下：假設數據是按升序排序的,對於給定值x,從序列的中間位置開始比較,如果當前位置值等於x,則查找成功；若x小於當前位置值,則在數列的前半段中查找；若x大於當前位置值則在數列的後半段中繼續查找,直到找到為止.由於是數組是預先排序好的,所以可以採用折半查詢的方式,每次拋掉待查詢部分的一半這樣,長度為N的數組,只需要log2N次查詢即可,2是對數的底.例如,長度為7的數組,最多隻需要3次就可以找到O(log2n)只是表示是log2N同一數量級,因為有個取整的問題,而且也有可能在查詢過程中就已經找到（也就是某個折半查詢點正好是待查詢數據）,這樣O(log2n)就是一個上限

⑻ 二分排序演算法是什麼 我聽說過快速排序 折半查找 怎麼沒聽說過二分排序 筆試題

其一：
二分排序是用二分法（就是折半查找）查找插入位置，來進行排序的。其實就是插入排序的一種修改。寫一段代碼解釋一下：
void MidInsertSort(int array[],int n)
{
int left,right,num;
int middle,j,i;
for(i = 1;i < n;i++)
{
left = 0;// 准備
right = i-1;
num = array[i];
while( right >= left)// 二分法查找插入位置
{
middle = ( left + right ) / 2; // 指向已排序好的中間位置
if( num < array[middle] )// 即將插入的元素應當在在左區間
right = middle-1;
else // 即將插入的元素應當在右區間
left = middle+1;
}
//每次查找完畢後，left總比right大一，a[left]總是存放第一個比num大的數，因此應從此處開始，每
//個元素右移一位，並將num存入a[left]中，這樣就保證了a[0...i]是排好序的
for( j = i-1;j >= left;j-- )// 後移排序碼大於R[i]的記錄
array[j+1] = array[j];
array[left] = num;// 插入
}
}
以上引自http://blog.sina.com.cn/s/blog_4b9eab320100kl08.html

其二：
如果是「二分歸並排序」，就應該是折半排序。。。

主流的說法就這兩種。

⑼ 二分法插入排序的演算法思想簡單描述：

二分法沒有排序，只有查找。所以當找到要插入的位置時。移動必須從最後一個記錄開始，向後移動一位，再移動倒數第2位，直到要插入的位置的記錄移後一位。

⑽ 什麼是二分法

二分法（Bisection method） 即一分為二的方法. 設[a，b]為R的閉區間. 逐次二分法就是造出如下的區間序列([an，bn])：a0=a，b0=b，且對任一自然數n，[an+1，bn+1]或者等於[an，cn]，或者等於[cn，bn]，其中cn表示[an，bn]的中點。

(10)排序演算法二分法擴展閱讀

典型演算法

演算法：當數據量很大適宜採用該方法。採用二分法查找時，數據需是排好序的。

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，

如果當前位置arr[k]值等於key，則查找成功；

若key小於當前位置值arr[k]，則在數列的前半段中查找,arr[low,mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1,high]，

直到找到為止,時間復雜度:O(log(n))。