綜述
- 插入排序：直接插入驾霜，折半插入案训，希爾排序；
- 交換排序：冒泡排序粪糙，快速排序强霎；
- 選擇排序：簡單選擇，堆排序蓉冈；
- 2路歸并
- 基數(shù)排序
- 外部排序
- 算法分析
1.插入排序
1.1直接插入：
思想
- 插入a城舞，向前尋找比自己大的結(jié)點；
- 將a保存在哨兵位置寞酿；
- 邊找邊向后移動家夺；
- 將哨兵元素賦值給找到的結(jié)點
代碼
void InsertSort(ElemType A[],int n)
{
int i,j;
for(i=2;i<=n;i++)
{
A[0]=A[i];
for(j=i-1;A[j]>A[0];j--) { A[j+1]=A[j]; }
A[j+1]=A[0];
注意最后一次循環(huán)，A[j+1]=A[j]執(zhí)行結(jié)束后伐弹，再次執(zhí)行j--拉馋；
所以需要A[J+1];
}
}
復(fù)雜度：
S：O（1）；
T：O（n^2）;
1.2 折半插入：
思想：查找時用折半
代碼：
void InsertSort(ElemType A[],int n)
{
int i,j,left,right,mid;
for(i=2;i<=n;i++)
{
A[0]=A[i];
left=1,right=i-1;
while(left<=right)
// 這里寫成left<right則不穩(wěn)定。等號是為了left和right相等時煌茴，繼續(xù)向右搜索是否有相等元素随闺，保持穩(wěn)定性。
{
mid= (left+right )/2;
if(A[mid]>A[0])right=mid-1;
else left=mid+1;
//A[mid]==A[0]為了保證穩(wěn)定性蔓腐，繼續(xù)右移矩乐；
}
出循環(huán)：則必有l(wèi)eft>right。
for(j=i-1;j>=left;--j) { A[j+1]=A[j] ;}
A[left]=A[0];
}
}
復(fù)雜度：
S:O(1);
T:O(n^2), 查找為(nlog(2,n));移動為(O(n^2))取最大
1.3希爾排序
思想：
按dk分組回论，組內(nèi)采用直接插入排序
image.png
代碼：
void ShellSort(ElemType A[],int n)
{
int i,j,dk;
for(dk=n/w;dk>=1;dk=dk/2)
{
for(i=dk+1;i<=n;i++)
{
if(A[i]<A[i-dk])
{
A[0]=A[i];
for(j=i-dk;j>0&&A[i]<[j];j=j-dk) { A[j+dk]=[j] ;}
A[j+dk]=A[0];
}
}
}
}
分析
- 復(fù)雜度： S：1绰精，T：n^2;
- 穩(wěn)定性：不穩(wěn)定；
- 適用性：直接插入（鏈表和順序表都可以）透葛，希爾和折半（只可順序）
2.交換排序
2.1冒泡排序
void BubbleSort(ElemType A[],int n)
{
int flag;
ElemType temp;
for(int i=0;i<n;i++)
{
flag=0;
for(int j=n-1;j>i;j--)
{
if(A[j]<A[j-1]])
{
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
flag=1;
}
}
if(!flag) return;
}
}
2.2快速排序
思想：
- 根據(jù)二叉插入法笨使，不難看出，即便搜索合適位置需要時間為Nlog(N),移動元素也需要N^2僚害，因此想要優(yōu)化時間復(fù)雜度硫椰，必須從移動元素和查詢合適位置兩方面雙管齊下。
- 快排基于分治法實現(xiàn)萨蚕。
步驟：
- partion函數(shù)：找到pivot靶草，將當(dāng)前序列分成兩部分。
- 遞歸分治岳遥。
- partition函數(shù)思想：一遍二分查位置一遍移動奕翔。兩個指針，若在后方出現(xiàn)小元素浩蓉，復(fù)制到前指針派继；若前方出現(xiàn)大元素，復(fù)制到后指針捻艳。
代碼：
void QuickSort(ElemType A[],int int left,int right )
{
int pivot=Partition(A,left,right);
QuickSort(A,left,pivot-1);
QuickSort(A,pivot+1,right);
}
ElemType Partition(ElemType A[],int left,int right)
{
int pivot=A[left];
while(left<right)
{
while(left<right&&A[right]>pivot) right--;
A[left]=A[right];
while(left<right&&A[left]<pivot) left++;
A[right]=A[left];
}
A[left]=pivot;
return left;
}
性能分析：
- 時間復(fù)雜度：平均(nlog(n)),最壞(n^2)驾窟；
若序列基本有序，快排將會較慢认轨。 - 穩(wěn)定性：不穩(wěn)定绅络。
王道習(xí)題
1.雙向冒泡
- 循環(huán)判定條件寫的比較巧妙: !flag&&left<right
void BubbleSort(ElemType A[],int n)
{
int left=0,right=n-1;
int flag;
while(!flag&&left<right)
{
flag=0;
for(int i=right;i>left;i--)
{
if(A[i]<A[i-1]) { swap(A[i],A[j]); flag=1; }
}
left++;
for(int j=left;j<right;j++)
{
if(A[j]>A[j+1]) { swap(A[j],A[j+1]; flag=1;) }
}
right--;
}
}
- 把所有奇數(shù)移動到偶數(shù)前面
- 將序列分成偶數(shù)奇數(shù)并隔開，很容易想到快排嘁字；
- 代碼：
ElemType Partition(ElemType A[],int left,int right)
{
int pivot=A[left];
while(left<right)
{
while(left<right&&!(A[right]%2)) right--;
A[left]=A[right];
while(left<right&&A[left]%2) left++;
A[right]=A[left];
}
A[left]=pivot;
return left;
}
- 隨機快排
思路
- 取隨機index j恩急，swap(A[j],A[left])，再執(zhí)行正臣脱眩快排衷恭；
void RQSort(ElemType A[],int left,int right)
{
int pivot=Partition(A,left,right);
RQSort(A,left,pivot-1);
RQSort(pivot+1,right);
}
int Partition(ElemType A[],int left,int right)
{
int Rindex=rand(left-right)+left;
swap(A[Rindex],A[left]);
ELemType pivot=A[left];
while(left<right)
{
while(left<right&&A[right]>pivot]) rigth--;
A[left]=A[right];
while(left<right&&A[left]<pivot) left++;
A[right]=A[left];
}
A[left]=pivot;
return left;
}
- 找到第k小的元素
- 快排修改版，若左邊的元素個數(shù)為k-1即pivot為所尋找的值
- 代碼
ElemType GetKth(ElemType A[],int left,int right)
{
Elem pivot=A[left];
int low_temp=low,right_temp=right;
while(left<right)
{
while(left<right&&A[right]>pivot]) rigth--;
A[left]=A[right];
while(left<right&&A[left]<pivot) left++;
A[right]=A[left];
}
if(==k-1)return pivot;
return pivot>k-1 ? GetKth(A,left_temp,left-1) : GetKth(A,left+1,right_temp);
}
- 將一個原序列劃分為兩個霍掺，數(shù)量差最小匾荆，類和差最大的子序列：
思想：
- 快排中的partition的改變，讓pivot接近n/2.ground杆烁；
代碼:
void setPartition(int A[],int n)
{
int pivot=A[0],left=0,right=n-1;
int p=left;
while(p!=n/2)
{
left=0,right=n-1;
while(left<right&&A[right]>pivot) right--;
A[left]=A[right];
while(left<right&&A[left<pivot]) right++;
A[right]=A[left];
p=left;
}
}
空間復(fù)雜度：O(1)
時間復(fù)雜度：O(n）
7. 荷蘭國旗
題干：將亂序多個的紅色牙丽，白色，藍色條塊排序成：紅-白-藍的荷蘭國旗兔魂。（即紅色的排在一起烤芦，白色的排在一起）
要求：時間復(fù)雜度為O(N)
思想：partition變體。
代碼：
typedef enum color {red,blue,white}color;
void Flag_arrange(color a[],int n)
{
int i=0,j=0,k=n-1;
while(j<=k)
{
switch(a[j])
{
case(red): swap(a[i],a[j];i++;j++);break;
case(white):j++;break;
case(blue) swap(a[j],a[k]);k--;break;
}
}
}
3.選擇排序：簡單選擇排序+堆排序
3.1簡單選擇排序：
- 思想 ：從子序列中找最小值（n）析校，放入子序列最前端构罗。子序列長度為1時停止。
- 代碼：
void SelectSort(ElemType A[],int n)
{
int min=0,i=0,j=0;
for(;i<n-1;i++)
for(int j=i;j<n-1;j++)
{
if(A[j]<A[min])min=j;
}
if(j!=i) {swap(A[i],A[min]);}
}
3.2堆排序：
- 思想：
以大根堆為例智玻，要建立一個根節(jié)點大于所有結(jié)點的樹遂唧，T為O（n）；
對堆排序的T為nlogn - 步驟：
對非葉節(jié)點(i<=len/2.ground)進行“下墜”操作吊奢，即HeadAdjust盖彭。
每次HeadAdjust比較次樹不會超過2(h-i),即小于2log(2,n);
將頂點元素和末尾元素換位，重新排序（樹結(jié)點數(shù)量減一）页滚。
A[0]暫存最大值
重復(fù)上述步驟召边，直到得到一棵先序遍歷結(jié)果為遞增序列的樹。
- 建堆
Void BuildHeap(Elemtype A[],int len)
{
for(int i=len/2;i>0;i--){HeadAdjust(A,i,len);}
}
void HeapSort(int A[],int len)
{
BuildHeap(A,len);
for(int i=len;i>1;i--)
{
swap(A[i],A[1]);
HeadAdjust(A,1,i-1);
}
}
下墜操作：
void HeadAdjust(int A[],int k,int len)
{
A[0]=A[k];
for(int i=2*k;i<=len;i=i*2)
{
if(i<len&&A[i]<A[i]+1)i++; //找到最大孩子裹驰；
if(A[0]>A[k])break; //若比最大孩子大隧熙，則k可以作為A[0]的存入點
// else
A[k]=A[i]; 否則，繼續(xù)向下尋找存入點幻林。// 同時將最大孩子上浮贞盯。
k=i;
}
A[k]=A[0];
}
下墜操作的簡圖：
image.png
時間復(fù)雜度：4n（建堆）+nlog(2,n)（排序）
王道習(xí)題：
-
算法分析，取出第k個最小元素之前的部分有序序列沪饺，采用什么方法：
簡單選擇排序：每次選擇最小邻悬，時間復(fù)雜度為kn。（每趟選出一個最小随闽，每趟為n）
冒泡排序：每次選擇最小父丰，時間復(fù)雜度為kn
堆排序：建堆的時間為4n，取k個最小的時間為klog2n掘宪，總時間為4n+log(2,n)蛾扇。
k和n很小時用簡單排序/冒泡排序，k和n很大時魏滚，用堆排序镀首。 -
單鏈表實現(xiàn)簡單選擇排序：
思路：頭插。
代碼:
void SelectSort(LinkList L)
{
Lnode* pre,*p,*tail,*s;
pre=L;
int flag;
while(pre!=null)
{
p=pre - > next,tail=p - > next;
flag=0;
while(tail!=null)
{
if(tail - > data<p - > data) {p=tail;s=p;tail=tail - > next; flag=1; }
else {tail=tail - > next;}
}
if(flag) break;
s - > next=p - > next;
p - > next=pre - > next;
pre=p;
}
}
- 判斷小根堆
思路：
- A[0]為temp鼠次。關(guān)鍵字的范圍是[1,n]
- 對所有分支結(jié)點更哄，判斷其與子節(jié)點的關(guān)鍵字芋齿。
代碼：
bool IsMinHeap(ElemType A[],int len)
{
if(len%0==0)//偶數(shù)長度，則節(jié)點有奇數(shù)個成翩。有一個但分支結(jié)點觅捆。
{
if(A[len]<A[len/2])return false;
for(int i=len/2-1;i>=1;i--)
{
if(A[i]<A[i/2])return false;
}
}
else
{
for(int i=len/2-1;i>=1;i--)
{
if(A[i]<A[i/2])return false;
}
}
return true;
}
4.歸并排序和基數(shù)排序
4.1 歸并排序
- 思想
分治 - 代碼：
void MergeSort(ElemType A[],int left,int right)
{
if(left<right)
{
int mid=(left+right)/2;
MergeSort(A,left,mid-1);
MerseSort(A,mid,right);
Merge(A,low,right,mid);
}
}
ElemType *B=(ElemType*)malloc(sizeof((n+1)*ElemType));
void Merge(ElemType A[],int left,right,mid)
{
for(int i=left;i<right;i++) { B[i]=A[i]; }
int i,j,k;
for( i=low,j=mid,k=i;j<=right;k++)
{
if(B[i]<B[j]){A[k]=B[i++];}
if(B[i>=B[j]]){A[k=B[j++];}
}
while(i<=mid) { A[k++]=B[i++]; }
while(j<=right) { A[K++]=b[j++]; } //元素相等，覆蓋后也相等麻敌，這里保證了排序的穩(wěn)定性
}
C++：
vector<int> B(A.size(),0);
void MergeSort(vector<int>& A,int left,int right){
int mid=(left+right)/2;
MergeSort(A,left,mid);
MergeSort(A,mid+1,right);
Merge(A,left,right,mid);
}
void Merge(vector<int>& A,int left,int right,int mid){
for(int i=left;i<right;i++) { B[i]=A[i]; }
int i,j,k;
for(i=left,j=mid,k=i;i<=right;k++){
if(B[i]>B[j]){A[k]=B[i++];}
else {A[k]=B[j++];}
}
while(i<=mid){A[k++]=B[left++];}
while(j<=right){A[k++]=B[j++];}
}
4.2 基數(shù)排序
思想：
- 不基于比較
- 關(guān)鍵字位數(shù)相同（若不同栅炒，高位補零）
- 高位優(yōu)先：MSD
- 低位優(yōu)先：LSD
效率
空間O(R)
時間O(d(n+r))
5.算法分析
-
時空復(fù)雜度和穩(wěn)定性：
image.png
-
- 2.階段結(jié)果：（第n躺的結(jié)果）
冒泡排序，堆排序术羔，選擇排序每趟可以產(chǎn)生最大值/最小值赢赊；
快排每趟可以確定一個元素的最終位置。（即一次partition可以確定pivot的最終位置）
