冒泡排序
基于“交換”的排序：根據序列中兩個元素關鍵字的比較結果來對換這兩個記錄在序列中的位置
//交換
void swap(int &a,int &b){int temp = a;a = b;b = temp;
}//冒泡排序
void BubbleSort(int A[],int n){for(int i=0;i<n-1;i++){bool flag = false; //表示本趟冒泡是否發生交換的標志for(int j = n-1;j>i;j--)if(A[j-1]>A[j]){swap(A[j-1],A[j]);flag = true;}if(flag == false) return ; //本趟遍歷后沒有發生交換，說明表已經有序}
}
算法性能分析
是否適用于鏈表？
適用，可從前往后“冒泡”，每?趟將更?的元素“冒”到鏈尾
快速排序
算法思想
//用第一個元素將待排序元素劃分為左右兩個部分
int Partition(int A[],int low,int high){int pivot = A[low];while(low<high){while(low<high&&A[high]>=pivot) --high;A[low] = A[high];while(low<high&&A[low]<=pivot) ++low;A[high] = A[low];}A[low] = pivot;return low;
}//快速排序
void QuickSort(int A[],int low,int high){if(low<high){int pivotpos = Partition(A,low,high);QuickSort(A,low,pivotpos);QuickSort(A,pivotpos,high);}
}
算法效率分析
時間復雜度=O(n*遞歸層數)
空間復雜度=O(遞歸層數)
| 時間復雜度 | 空間復雜度 | |
|---|---|---|
| 最好 | O(nlog2n) | O(log2n) |
| 最壞 | O(n2) | O(n) |
若每?次選中的“樞軸”將待排序序列劃分為很不均勻的兩個部分，則會導致遞歸深度增加，算法效率變低
若初始序列有序或逆序，則快速排序的性能最差（因為每次選擇的都是最靠邊的元素）
若每?次選中的“樞軸”將待排序序列劃分為均勻的兩個部分，則遞歸深度最?，算法效率最?
快速排序算法優化思路：盡量選擇可以把數據中分的樞軸元素。
eg：①選頭、中、尾三個位置的元素，取中間值作為樞軸元素；②隨機選?個元素作為樞軸元素
注：408原題中說，對所有尚未確定最終位置的所有元素進行?遍處理稱為“?趟”排序，因此?次“劃分”≠?趟排序。
?次劃分可以確定?個元素的最終位置，而?趟排序也許可以確定多個元素的最終位置。
