排序的概念
1、排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作，
2、穩定性：假定在待排序的記錄序列中，存在多個具有相同關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序演算法是穩定的；否則稱為不穩定的，
3、內部排序：資料元素全部放在記憶體中的排序，
4、外部排序：資料元素太多不能同時放在記憶體中，根據排序程序的要求不能在內外存之間移動資料的排序
常見排序如下圖
插入排序
基本思想：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 ，
直接插入排序
程序：當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移，
實體程序
C語言代碼
void InsertSort(int *a,int n){
assert(a);
for(int i=0;i<n-1;i++){//控制插入的趟數，因為第一個元素有序，所以趟數是n-1
int end=i;
int temp=a[end+1];
while(end>=0&&a[end]>temp){//單趟插入排序,當前元素小于temp時直接插入到當前元素的下一個位置，因為后面所有的元素都往后移動了一個位置
a[end+1]=a[end];
end--;
}
a[end+1]=temp;
}
}
直接插入排序特性總結
1、時間復雜度：平均時間復雜度：O(N^ 2)，最好情況：O(n)，最壞情況：O(n^2)，當元素序列接近有序時，直接插入排序時間效率最高，可以快排的小區間優化，
2、空間復雜度：O(1)，
3、穩定性：穩定
希爾排序(縮小增量排序)
程序：先選定一個整數作為距離，把待排序序列中所有距離相同的分成一個組，并對每一組內的元素進行排序，然后，縮小距離，重復上述分組和排序的作業，當距離>1時為預排序，當距離=1時即是直接插入排序，整個序列即為有序序列，
實體程序
C語言代碼
void ShellSort(int *a,int n) {
// 1.gap>1相當于預排序
// 2.gap=1相當于直接插入排序
int gap = n;
while (gap>1) {
gap = gap / 3 + 1; //+1保證了最后一次一定要為1
for (int i = 0; i < n - gap;i++) {
int end = i;
int temp = a[end + gap];
while (end >= 0) {
if (a[end] > temp) {
a[end+gap] = a[end];
end -= gap;
}
else break;
}
a[end + gap] = temp;
}
}
}
希爾排序特性總結
1、時間復雜度：平均時間復雜度：O(NlogN)，最好情況：O(n^ 1.3)，最壞情況：O(n^2)，
2、空間復雜度：O(1)，
3、穩定性：不穩定
4、希爾排序是對直接插入排序的優化
5、gap越大，前面大的資料可以更快的到后面，后面小的數，可以更快的到前面，gap越大，越不接近有序，gap越小，越接近有序，如果gap=1，就是直接插入排序，那么對于接近有序的序列進行直接插入排序演算法時間效率是很高效的，所以希爾排序對直接插入排序做了一個很好的優化，
選擇排序
基本思想：每一次從待排序的資料元素中選出最大(最小)的一個元素，存放在待排序序列的末尾(起始)位置，直到全部待排序的資料元素排完，
選擇排序
程序：
■1. 在元素集合array[i]–array[n-1]中選擇key最大(最小)的資料元素，
■2. 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換，
■3. 在剩余的集合中重復上述程序，直到集合中只剩余一個元素，
實體程序
C語言代碼
//升序排序
void SelectSort(int* a, int n) {
assert(a);
int end = n-1;//控制趟數
while (end) {
int max = 0;
for (int i = 0; i <= end; i++) {//在剩余陣列序列中選擇最大元素
if (a[max] < a[i]) {
max = i;
}
}
swap(a + max, a + end);
end--;
}
}
選擇排序特性總結
1、時間復雜度：平均時間復雜度：O(n^ 2)，最好情況：O(n^ 2)，最壞情況：O(n^2)，
2、空間復雜度：O(1)，
3、穩定性：不穩定
堆排序
堆排序詳解請參見我另外一篇博客：圖解二叉堆：堆排序
交換排序
思想：交換：就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，
冒泡排序
程序：若是升序排列則是將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動，之所以叫冒泡排序是大的值不斷往后移動就像泡一樣往后冒，
實體程序
C語言代碼
void BubbleSort(int* a, int n) {
assert(a);
int end = n;//控制趟數
while (end) {
int exchange=1;
for (int i = 1; i < end; i++) { //每次將最大冒到剩余陣列序列的最后一個位置
if (a[i] < a[i-1]) {
swap(a + i, a + i - 1);
exchange=0;
}
}
if(exchange) break;
end--;
}
}
冒泡排序特性總結
1、時間復雜度：平均時間復雜度：O(N^ 2)，最好情況：O(n)，最壞情況：O(n^2)，
2、空間復雜度：O(1)，
3、穩定性：穩定，
快速排序
快速排序詳解請參見我另外一篇博客：快速排序(雙指標法、挖坑法、前后指標法)遞回、非遞回實作
歸并排序
歸并排序詳解請參見我另外一篇博客：歸并排序(遞回實作、非遞回實作)、磁盤中的外排序，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255212.html
標籤：其他