快速排序是大多數(shù)語言內(nèi)置 sort 函數(shù)的默認(rèn)實現(xiàn)方式，簡單可分為兩路排序和三路排序，我在相關(guān)資料中，發(fā)現(xiàn)兩路排序也有多種實現(xiàn)方式。
我們提供的服務(wù)有：成都網(wǎng)站設(shè)計、網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、臨高ssl等。為數(shù)千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的臨高網(wǎng)站制作公司
兩路快排的邏輯
這個名詞來自于 b 站的評論，這個快排思路很容易理解，非常適合入門
大體上和第一個版本差不多，但是函數(shù)更加簡潔了，
這個版本是所有快速排序中，看起來比較難以理解，只有一個指針，從左到右滑動，設(shè)計非常巧妙。
這邊測試了四種情況，中間值最優(yōu)。
用了3個指針，表示小于，等于，大于三個部分，從而減少相等的數(shù)在其中來回交換。
由此可見快速排序是一種不穩(wěn)定的排序，對于數(shù)據(jù)本身是有要求，對于 pivot 如何取也是有要求，屬于經(jīng)驗取值了，如果對于源數(shù)據(jù)是逆序的情形，快排會退化成冒泡。
2021年03月18日22:24 更新
時間：
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空間：
O(1)
它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
n個記錄的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
時間：
平均O(n 2 ) 最差O(n 2 ) 最好O(n 2 )
空間：
O(1)
它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
一般來說，插入排序都采用in-place在數(shù)組上實現(xiàn)。具體算法描述如下：
時間：
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空間：
O(1)
快速排序的基本思想： 二分遞歸 ，通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。
快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：
我們可以通過雙指針在O(n)的時間復(fù)雜度內(nèi)獲取合適的 j
我們設(shè)立兩個指針 i 和 j，同時設(shè)置一個標(biāo)志值 arr[low]，一般來說，標(biāo)志值取數(shù)組第一個元素
上述算法結(jié)束之后，j 所在的位置即為我們尋找的 j
4.3 時間空間復(fù)雜度
時間：
平均O(nlog 2 n) 最差O(n 2 ) 最好O(nlog 2 n)
空間：
O(1)
算法思想?yún)⒖甲裕?/p>
本文介紹一些Go語言的基礎(chǔ)語法。
先來看一個簡單的go語言代碼：
go語言的注釋方法：
代碼執(zhí)行結(jié)果：
下面來進(jìn)一步介紹go的基礎(chǔ)語法。
go語言中格式化輸出可以使用 fmt 和 log 這兩個標(biāo)準(zhǔn)庫，
常用方法：
示例代碼：
執(zhí)行結(jié)果：
更多格式化方法可以訪問中的fmt包。
log包實現(xiàn)了簡單的日志服務(wù)，也提供了一些格式化輸出的方法。
執(zhí)行結(jié)果：
下面來介紹一下go的數(shù)據(jù)類型
下表列出了go語言的數(shù)據(jù)類型：
int、float、bool、string、數(shù)組和struct屬于值類型，這些類型的變量直接指向存在內(nèi)存中的值；slice、map、chan、pointer等是引用類型，存儲的是一個地址，這個地址存儲最終的值。
常量是在程序編譯時就確定下來的值，程序運行時無法改變。
執(zhí)行結(jié)果：
執(zhí)行結(jié)果：
Go 語言的運算符主要包括算術(shù)運算符、關(guān)系運算符、邏輯運算符、位運算符、賦值運算符以及指針相關(guān)運算符。
算術(shù)運算符：
關(guān)系運算符：
邏輯運算符：
位運算符：
賦值運算符：
指針相關(guān)運算符：
下面介紹一下go語言中的if語句和switch語句。另外還有一種控制語句叫select語句，通常與通道聯(lián)用，這里不做介紹。
if語法格式如下：
if ... else ：
else if：
示例代碼：
語法格式：
另外，添加 fallthrough 會強(qiáng)制執(zhí)行后面的 case 語句，不管下一條case語句是否為true。
示例代碼：
執(zhí)行結(jié)果：
下面介紹幾種循環(huán)語句：
執(zhí)行結(jié)果：
執(zhí)行結(jié)果：
也可以通過標(biāo)記退出循環(huán)：
--THE END--
終于編寫出來了，我寫了兩種，你看看：下面是代碼：
/*非遞歸算法1
遞歸算法的開銷很大，所以在下編了一個非遞歸的，算法描述如下：
A non-recursive version of quick sort using stack:
There are 2 stacks, namely one which stores the start of
a subarray and the other which stores the end of the
subarray.
STEP 1: while the subarray contains more than one element
,i.e. from Do {
SUBSTEP 1. pivot=Partion(subarray);
SUBSTEP 2. keep track of the right half of the current
subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
SUBSTEP 3. go on to deal with the left half of
the current subarray i.e. to=pivot-1
}
STEP 2: if(neither of the stacks is empty)
Get a new subarray to deal with from the stacks.
i.e. start=pop(stackFrom); to=pop(stackTo);
STEP 3: both stacks are empty, and array has
been sorted. The program ends.
*/*/
void UnrecQuicksort(int q[],int low,int high)
{stack s1;br/stacks2;br/ s1.push(low);br/ s2.push(high);br/ int tl,th,p;br/ while(!s1.empty() !s2.empty())br/ {tl=s1.top();th=s2.top();br/ s1.pop();s2.pop();br/ if(tl=th) continue;br/ p=partition(q,tl,th);br/ s1.push(tl);s1.push(p+1);br/ s2.push(p-1);s2.push(th);br/ }
}
/*非遞歸算法2
要把遞歸算法改寫成非遞歸算法，可引進(jìn)一個棧，這個棧的大小取決于遞歸調(diào)用的深度，最
多不會超過n，如果每次都選較大的部分進(jìn)棧，處理較短的部分，遞歸深度最多不超過log2n
，也就是說快速排序需要的附加存儲開銷為O（log2n）。
*/
void UnrecQuicksort2(int q[],int low,int high)
{int *a;br/ int top=0,i,j,p;br/ a=new int[high-low+1];br/ if(a==NULL) return;br/ a[top++]=low;br/ a[top++]=high;br/ while(top0)br/ {i=a[--top];br/ j=a[--top];br/ while(j {p=partition(q,j,i);br/ if(p-j {//先分割前部,后部進(jìn)棧br/a[top++]=p+1;br/ a[top++]=i;br/ i=p-1;br/ }
else
{//先分割后部,前部進(jìn)棧
a[top++]=j;
a[top++]=p-1;
j=p+1;
}
}
}
}
/*打印輸出*/
void display(int p[],int len)
{for(int i=0;i cout}
/*測試*/
int _tmain(int argc, _TCHAR* argv[])
{int a[]={49,65,97,12,23,41,56,14};
quicksort(a,0,7);
//UnrecQuicksort(a,0,7);
//UnrecQuicksort2(a,0,7);
display(a,8);
return 0;
}
GO是編譯性語言，所以函數(shù)的順序是無關(guān)緊要的，為了方便閱讀，建議入口函數(shù) main 寫在最前面，其余函數(shù)按照功能需要進(jìn)行排列
GO的函數(shù) 不支持嵌套，重載和默認(rèn)參數(shù)
GO的函數(shù) 支持 無需聲明變量，可變長度，多返回值，匿名，閉包等
GO的函數(shù)用 func 來聲明，且左大括號 { 不能另起一行
一個簡單的示例：
輸出為：
參數(shù)：可以傳0個或多個值來供自己用
返回：通過用 return 來進(jìn)行返回
輸出為：
上面就是一個典型的多參數(shù)傳遞與多返回值
對例子的說明：
按值傳遞：是對某個變量進(jìn)行復(fù)制，不能更改原變量的值
引用傳遞：相當(dāng)于按指針傳遞，可以同時改變原來的值，并且消耗的內(nèi)存會更少，只有4或8個字節(jié)的消耗
在上例中，返回值 (d int, e int, f int) { 是進(jìn)行了命名，如果不想命名可以寫成 (int,int,int){ ,返回的結(jié)果都是一樣的，但要注意:
當(dāng)返回了多個值，我們某些變量不想要，或?qū)嶋H用不到，我們可以使用 _ 來補(bǔ)位，例如上例的返回我們可以寫成 d,_,f := test(a,b,c) ，我們不想要中間的返回值，可以以這種形式來舍棄掉
在參數(shù)后面以 變量 ... type 這種形式的，我們就要以判斷出這是一個可變長度的參數(shù)
輸出為：
在上例中， strs ...string 中， strs 的實際值是b,c,d,e,這就是一個最簡單的傳遞可變長度的參數(shù)的例子，更多一些演變的形式，都非常類似
在GO中 defer 關(guān)鍵字非常重要，相當(dāng)于面相對像中的析構(gòu)函數(shù)，也就是在某個函數(shù)執(zhí)行完成后，GO會自動這個；
如果在多層循環(huán)中函數(shù)里，都定義了 defer ,那么它的執(zhí)行順序是先進(jìn)后出；
當(dāng)某個函數(shù)出現(xiàn)嚴(yán)重錯誤時， defer 也會被調(diào)用
輸出為
這是一個最簡單的測試了，當(dāng)然還有更復(fù)雜的調(diào)用，比如調(diào)試程序時，判斷是哪個函數(shù)出了問題，完全可以根據(jù) defer 打印出來的內(nèi)容來進(jìn)行判斷，非?？焖?，這種留給你們?nèi)崿F(xiàn)
一個函數(shù)在函數(shù)體內(nèi)自己調(diào)用自己我們稱之為遞歸函數(shù)，在做遞歸調(diào)用時，經(jīng)常會將內(nèi)存給占滿，這是非常要注意的，常用的比如，快速排序就是用的遞歸調(diào)用
本篇重點介紹了GO函數(shù)(func)的聲明與使用，下一篇將介紹GO的結(jié)構(gòu) struct
重慶分公司
重慶分公司
