Go語言 排序與搜索切片

Go語言標(biāo)準(zhǔn)庫中提供了sort包對整型，浮點(diǎn)型，字符串型切片進(jìn)行排序，檢查一個(gè)切片是否排好序，使用二分法搜索函數(shù)在一個(gè)有序切片中搜索一個(gè)元素等功能。

作為一家“創(chuàng)意+整合+營銷”的成都網(wǎng)站建設(shè)機(jī)構(gòu)，我們在業(yè)內(nèi)良好的客戶口碑。創(chuàng)新互聯(lián)建站提供從前期的網(wǎng)站品牌分析策劃、網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、創(chuàng)意表現(xiàn)、網(wǎng)頁制作、系統(tǒng)開發(fā)以及后續(xù)網(wǎng)站營銷運(yùn)營等一系列服務(wù)，幫助企業(yè)打造創(chuàng)新的互聯(lián)網(wǎng)品牌經(jīng)營模式與有效的網(wǎng)絡(luò)營銷方法,創(chuàng)造更大的價(jià)值。

關(guān)于sort包內(nèi)的函數(shù)說明與使用，請查看

在這里簡單講幾個(gè)sort包中常用的函數(shù)

在Go語言中，對字符串的排序都是按照字節(jié)排序，也就是說在對字符串排序時(shí)是區(qū)分大小寫的。

二分搜索算法

Go語言中提供了一個(gè)使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比較㏒?n個(gè)元素，其中n為切片中元素的總數(shù)。

sort.Search(size,fn)函數(shù)接受兩個(gè)參數(shù)：所處理的切片的長度和一個(gè)將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個(gè)閉包，如果該有序切片是升序排列，那么在判斷時(shí)使用 有序切片的元素 = 目標(biāo)元素。該函數(shù)返回一個(gè)int值，表示與目標(biāo)元素相同的切片元素的索引。

在切片中查找出某個(gè)與目標(biāo)字符串相同的元素索引

完善程序（二分查找法插入元素）

struct list{int key;};/*定義結(jié)構(gòu)類型*/

typedef struct list SeqList,DataType;

void BinInsert(SeqList r[],int *n,DataType x)

{ int low=1,high=*n,mid,i;

while(low=high)

{ mid=(low+high)/2;

if (x.keyr[mid].key)high=mid-1;

else low=mid+1;

}

for(i=*n;i=mid;i--)

r[i+1]=r[i];

r[mid].key=x.key;/*插入元素*/

}

main()

{

SeqList a[11];int i,n;DataType y;

n=0;

for(i=0;i10;i++)/*輸入數(shù)據(jù)*/

{a[i].key=i+1;n++;}

printf("before sort :");

for(i=0;i10;i++)/*排序前的數(shù)組*/

{printf("%4d",a[i].key);};

printf("\ninput elem(y)=");/*輸入要插入的元素*/

scanf("%d",y.key);

BinInsert(a,n,y);

printf("\nafter sort :");

for(i=0;i11;i++)/*輸出排序后的數(shù)組*/

printf("%4d",a[i].key);getch();

}

二分查找和快速排序

二分

package stack;

public class HalfSearch {

static int a[]={1,3,5,98,8,9,4,38,12};

public static int halfSeacrh(int[] a,int number){//二分查找

HalfSearch hs=new HalfSearch();

hs.bubbleSort(a);

int startPostion=0;

int endPostion=a.length-1;

int postion=(startPostion+endPostion)/2;

while(startPostionendPostion){

if(a[postion]==number)

return postion;

else if(a[postion]number){

startPostion=postion+1;

}

else if(a[postion]number){

endPostion=postion-1;

}

postion=startPostion+endPostion;

}

return -1;

}

public static void bubbleSort(int a[]){

int temp=0;

for(int i=0;ia.length;i++){

for(int j=i+1;ja.length;j++){

if(a[i]a[j]){

temp=a[i];

a[i]=a[j];

a[j]=temp;

}

}

}

}

public static void main(String[] args) {

System.out.println(halfSeacrh(a,8));

}

}

快速：templateclass elemtype

void arrayelemtype::sort(int low,int high)

{

if(low=high) return;

int lo=high+1;

elemtype elem=_ia[low];

for( ; ; ) {

while(_ia[++lo]elem lohigh);

while(_ia[--hi]elem hilo);

if(lohi) swap(lo,hi);

else break;

}

swap(low,hi);

sort(low,hi-1);

sort(hi+1,high);

}

對比順序查找、二分查找和哈希查找算法,它們各自的特點(diǎn)是什么?

順序查找,二分查找和哈希查找算法,它們各自的特點(diǎn)是：

1.對比順序查找的特點(diǎn)就是從表的第一個(gè)元素開始一個(gè)一個(gè)向下查找，如果有和目標(biāo)一致的元素，查找成功;如果到最后一個(gè)元素仍沒有目標(biāo)元素，則查找失敗。

2.二分查找的特點(diǎn)就是從表中間開始查找目標(biāo)元素。如果找到一致元素，則查找成功。如果中間元素比目標(biāo)元素小，則仍用二分查找方法查找表的后半部分(表是遞增排列的)，反之中間元素比目標(biāo)元素大，則查找表的前半部分。

3.哈希算法的特點(diǎn)是是使用給定數(shù)據(jù)構(gòu)造哈希表，然后在哈希表上進(jìn)行查找的一種算法。先給定一個(gè)值，然后根據(jù)哈希函數(shù)求得哈希地址，再根據(jù)哈希地址查找到要找的元素。是通過數(shù)據(jù)元素的存儲地址進(jìn)行查找的一種算法。

二分查找算法

二分查找算法，該算法要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。如果一個(gè)序列是無序的或者是鏈表，那么該序列就不能使用二分查找。

二分查找算法原理：若待查序列為空，則返回-1，并退出算法；若待查序列不為空，則將它的中間元素與目標(biāo)數(shù)值進(jìn)行比較，判斷是否相等；若相等，則返回中間元素索引，并退出算法；此時(shí)已查找成功。若不相等，則比較中間元素與目標(biāo)數(shù)值的大小。

若中間元素目標(biāo)數(shù)值，則將當(dāng)前序列的前半部分作為新的待查序列；若中間元素目標(biāo)數(shù)值，則將當(dāng)前序列的后半部分作為新的待查序列；在新的序列上重新從第（1）步開始查找。

二分法查找的思路：首先，從數(shù)組的中間元素開始搜索，如果該元素是目標(biāo)元素，則搜索過程結(jié)束，否則執(zhí)行下一步。如果目標(biāo)元素大于/小于中間元素，則在數(shù)組大于/小于中間元素的那一半?yún)^(qū)域查找，然后重復(fù)步驟（1）的操作。如果某一步數(shù)組為空，則表示找不到目標(biāo)元素。

二分查找的一個(gè)技巧是：不要出現(xiàn)else，而是把所有情況用else，if寫清楚，這樣可以清楚地展現(xiàn)所有細(xì)節(jié)。本文都會使用else，if，旨在講清楚，讀者理解后可自行簡化。

二分查找法的具體算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。它的基本思想是，將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果xa[n/2]，則我們只要在數(shù)組a的左半部繼續(xù)搜索x（這里假設(shè)數(shù)組元素呈升序排列）。如果xa[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解，但是要寫一個(gè)正確的二分搜索算法也不是一件簡單的事。第一個(gè)二分搜索算法早在1946年就出現(xiàn)了，但是第一個(gè)完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計(jì)算機(jī)專家不能在2小時(shí)內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準(zhǔn)確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實(shí)整理后可以發(fā)現(xiàn)它的具體算法是很直觀的，我們可用C++描述如下：

templateclass Type

int BinarySearch(Type a[],const Type x,int n)

{

int left=0;

int right=n-1;

while(left=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (xa[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數(shù)BinarySearch在a[0]=a[1]=...=a[n-1]共n個(gè)升序排列的元素中搜索x,找到x時(shí)返回其在數(shù)組中的位置，否則返回-1。容易看出，每執(zhí)行一次while循環(huán)，待搜索數(shù)組的大小減少一半,因此整個(gè)算法在最壞情況下的時(shí)間復(fù)雜度為O(log n)。在數(shù)據(jù)量很大的時(shí)候，它的線性查找在時(shí)間復(fù)雜度上的優(yōu)劣一目了然。

本文名稱：GO語言二分查找算法,詳解二分查找算法
鏈接URL：http://chinadenli.net/article49/dsiddhh.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、面包屑導(dǎo)航、響應(yīng)式網(wǎng)站、網(wǎng)頁設(shè)計(jì)公司、搜索引擎優(yōu)化、營銷型網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)