九種經典排序算法匯總
來源：程序員人生 發布時間：2016-07-06 08:51:43 閱讀次數：2650次
/***********************************************************
總結各種排序算法包括但不限于：
1. 插入排序類
1.1 直接插入排序
1.2 2分插入排序
1.3 希爾排序
2. 交換排序類
2.1 冒泡排序
2.2 快速排序
3. 選擇排序
3.1 直接選擇排序
3.2 堆排序
4. 歸并排序
5. 基數排序
以上所有排序算法的實現均為將整形數組data遞增排序
************************************************************/
#include#include
using namespace std;
/********************** 1 直接插入排序********************************
空間復雜度：只有輔助變量， 沒有與問題范圍相干的輔存消耗，O(1)
時間復雜度：最好情況，初始數組為正序（此處為遞增），O(n)；最壞情況，初始數組為反
序，O(n2)；平均時間復雜度為O(n2).
穩定性：當data[i]=datda[i⑴]時，相對位置不變，所以是穩定的排序
思想：將原序列分為有序區和無序區，每次外部循環將無序區的第1個元素插入到有序區的適
當位置，同時有序區元素加1，無序區元素減1，這樣直到無序區的元素為0
*******************************************************************/
void insertSort(int data[], int n)
{
int i, j;
int tmp;
for (i = 1; i < n; ++i) { tmp = data[i]; j = i - 1; while (j >= 0 && tmp < data[j]) { data[j + 1] = data[j]; --j; } //若j<0則tmp是有序區的最小元素，若tmp>=data[j]則將tmp放在data[j]的
//后面data[j+1]處
data[j + 1] = tmp;
}
}
/************************ 2 2分（折半）插入排序 ***********************
時空復雜度及穩定性與上面是1樣的
思想：對有序的序列2分查找效力比順序查找高很多，基于此，在將無序區的第1個元素插
入到有序區相應位置時，用2分查找尋覓該位置而不是順序查找，可以減少關
鍵字比較的次數但是關鍵字移動的次數依然是沒有改變的，所以其實際的效果與直接插
入排序相當，只需注意2分查找思想的應用。
*******************************************************************/
void biInsertSort(int data[], int n)
{
int i, j, low, high, mid;
int tmp;
for (i = 1; i < n; ++i) { tmp = data[i]; low = 0, high = i - 1; while (low <= high) { mid = (low + high) / 2; if (tmp < data[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= high + 1; --j)//high+1 is mid
data[j + 1] = data[j];
data[high + 1] = tmp;
}
}
/************************* 3 希爾排序 ********************************
空間復雜度：只用到了i,j,gap,tmp4個輔助變量，與問題范圍無關，空間復雜度為O(1).
時間復雜度：分析較復雜，1般認為平均時間復雜度為O(n^1.3).
穩定性：不穩定
思想：本質上還是屬于插入排序，只不過是先對序列分組，然后組內直接插入，同時，分組數
由多到少，組內元素由少到多，順序性由差到好，直到最后1步組間距為1時，
直接插入排序的數組已基本有序了
*******************************************************************/
void shellSort(int data[], int n)
{
int i, j, gap;
int tmp;
gap = n / 2;
while (gap > 0)
{
//這樣記憶，全部for循環其實就是直接插入排序的進程，只不過將直接插入排序
//的1->gap罷了，最后當gap=1的時候就是直接插入排序了。
for (i = gap; i < n; ++i) { tmp = data[i]; j = i - gap; while (j >= 0 && tmp < data[j]) { data[j + gap] = data[j]; j = j - gap; } data[j + gap] = tmp; } gap = gap / 2; } } /*************************** 4 冒泡排序 ****************************** 空間復雜度：只有3個輔助變量，與問題范圍無關，空間復雜度為O(1) 時間復雜度：最好情況，數組本身是正序的，O(n)；最壞情況，數組是反序的，O(n^2)；平 均時間復雜度為O(n^2)。 穩定性：穩定 思想：將數組頭部看成水面，數組尾部看成水底，最小（或最大）的元素上浮（或下沉）直到 結束，采取的是比較元素大小然后交換元素值的思想，每次都選擇未排序的 元素中最小或最大元素投遞指定的位置。 *******************************************************************/ //經典冒泡排序算法，以后以這個為準 void bubbleSort(int data[], int n) { int i, j, tmp, flag; for (i = 0; i < n - 1; ++i) { flag = 0; for (j = 0; j < n - i - 1; ++j) { if (data[j] > data[j + 1])
{
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
flag = 1;
}
}
if (flag == 0)
return;
}
}
//最小元素上浮
void bubbleSort1(int data[], int n)
{
int tmp, flag;
for (int i = 0; i < n - 1; ++i) { flag = 0; for (int j = n - 1; j > i; --j)
{
if (data[j] < data[j - 1]) { tmp = data[j]; data[j] = data[j - 1]; data[j - 1] = tmp; flag = 1; } } if (flag == 0)//no swap in the circulation return; } } //最大元素下沉（備選方案，與上面是1樣的） void bubbleSort2(int data[], int n) { int tmp, flag; for (int i = n⑴; i > 0; --i)
{
flag = 0;
for (int j = 0; j < i; ++j) { if (data[j] > data[j + 1])
{
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
flag = 1;
}
}
if (flag == 0)
return;
}
}
/***************************** 5 快速排序 ****************************
空間復雜度：主要是遞歸時所需的棧空間，平均空間復雜度為O(nlongn)。
時間復雜度：主要的時間都花費在劃分上面，最好情況，每次劃分的基準都是無序區的‘中
值’記錄，O(nlogn);最壞情況，原數組本身是有序的，此時O(n^2)。
平均時間復雜度為O(nlogn)。
穩定性： 不穩定
思想：分治的思想，將大問題轉化為小問題，遞歸的思想，最重要的進程就是劃分，劃分結束
了，數組也就排好序了，快速排序是排序算法中非常重要的1種
*******************************************************************/
//快排，數據結構書上的方法,遞歸，以后以這個為準
void quickSort(int data[], int start, int end)
{
int i = start, j = end;
int pivot;
if (start < end) { //每次遞歸都取無序區的第1個元素作為中心基準，這個地方可以改進為隨機的方法 pivot = data[start]; while (i != j) { while (j>i && data[j] > pivot)
--j;
data[i] = data[j];
while (i < j && data[i] < pivot) ++i; data[j] = data[i]; } data[i] = pivot; quickSort(data, start, i - 1); quickSort(data, i + 1, end); } } //另外1個版本是將劃分（上面if里面的代碼）進程單獨成為1個partition函數,同時采樣隨機化快排思想(劍指offer) int randomInRange(int s, int t) { srand((unsigned int)time(NULL)); return s + rand() % (t - s + 1); } void swap(int* left, int* right) { int tmp = *left; *left = *right; *right = tmp; } int partition(int data[], int length, int start, int end) { if (data == NULL || start < 0 || end >= length)
throw new std::exception("invalid parameters");
int index = randomInRange(start, end);
swap(&data[index], &data[end]);
int small = start - 1;
for (index = start; index < end; ++index) { if (data[index] < data[end]) { ++small; if (small != index) swap(&data[index], &data[small]); } } ++small; swap(&data[small], &data[end]); return small; } void quickSort1(int data[], int length, int start, int end) { if (start == end) return; int index = partition(data, length, start, end); if (index > start)
quickSort1(data, length, start, index - 1);
if (index < end) quickSort1(data, length, index + 1, end); } /*************************** 6 直接選擇排序 ************************** 空間復雜度：只用到了i,j,k,tmp4個輔助變量，故空間復雜度為O(1). 時間復雜度：不管表的初始狀態如何，比較次數都到達O(n^2),故直接選擇排序的最好和最壞 時間復雜度都是O(n^2). 穩定性：不穩定，如將{5，3，2，5，4，1}排序，第1趟就改變了兩個5的相對位置。可以 看成是交換排序和直接插入排序的綜合，但是直接插入和冒泡排序都是穩定的，而該 算法是不穩定的 思想：每趟從待排序的記錄當選擇關鍵字最小的記錄，順序放在已排好序子表的最后，知道 全部記錄排序終了 適用性：合適從大量記錄當選擇1部份排序記錄，如從10000個記錄當選擇關鍵字大小為前10 的記錄 *******************************************************************/ void selectSort(int data[], int n) { int tmp, k; for (int i = 0; i < n - 1; ++i) { k = i; for (int j = i + 1; j < n; ++j) { if (data[j] < data[k]) k = j; } if (k != i)//若k=i則證明已是有序的了 { tmp = data[i]; data[i] = data[k]; data[k] = tmp; } } } /****************************** 7 堆排序 **************************** 空間復雜度：只用到了4個輔助變量，空間復雜度是O(1). 時間復雜度：最好，最壞，和平均時間復雜度都是O(nlogn). 穩定性：不穩定 思想：本質上是1種樹形選擇排序思想，將原數組看成為1個完全2叉樹的順序存儲結構，利 用完全2叉樹中雙親節點和孩子節點之間的內在關系，在當前無序區當選擇關鍵字 最大（大根堆）或最小（小根堆）的記錄移動到數組的末尾，然后對剩余的元素作同 樣的操作 適用性：不適合記錄數較少的表，與直接選擇排序算法類似 *******************************************************************/ //算法分為兩個主要部份，堆調劑（采取挑選算法），與排序 //建立大根堆，每次將最大的元素移動到末尾 void heapAdjust(int data[], int start, int end) { int tmp = data[start]; for (int i = 2 * start + 1; i <= end; i *= 2){ //這個i data[i])
break;
data[start] = data[i];
start = i;
}
data[start] = tmp;
}
void heapAdjust1(int data[], int low, int high)
{
int i = low, j = 2 * i+1;
int tmp = data[i];
while (j <= high) { if (j < high && data[j] < data[j + 1]) ++j; if (tmp < data[j]) { data[i] = data[j]; i = j; j = 2 * i; } else break; } data[i] = tmp; } void heapSort(int data[], int n) { int i; int tmp; //建立初始堆 for (i = n / 2; i >= 0; --i)
{
heapAdjust(data, i, n⑴);
}
//堆排序進程
for (int i = n⑴; i >= 0; --i)
{
//交換堆頂和最后1個元素
tmp = data[0];
data[0] = data[i];
data[i] = tmp;
//調劑堆滿足大根堆的性質
heapAdjust(data, 0, i - 1);
}
}
/*************************** 8 歸并排序 ******************************
空間復雜度：O(n),需要1個輔助的數組來寄存合并兩個有序表以后生成的新表，故歸并排序不是就地排序
時間復雜度：最好，最壞，平均時間復雜度均是O(nlogn)
穩定性：歸并排序是穩定的排序算法
思想：將兩個或兩個以上的有序表合并為1個新的有序表，遞歸的思想
*******************************************************************/
////迭代版本,有問題
//void mergeSort_iter(int data[], int n)
//{
// int *b = new int[n];
// int *a = data;
// //外層for循環，1共進行logn趟歸并
// for (int seg = 1; seg < n; seg += seg) // { // //1趟歸并排序 // for (int start = 0; start < n; start += seg + seg) // { // int low = start, mid = (start + seg) < n ? (start + seg) : n, high = (start + seg + seg) < n ? (start + seg + seg) : n; // int k = low; // int start1 = low, end1 = mid; // int start2 = mid, end2 = high; // while (start1 < end1 && start2 < end2) // b[k++] = a[start1] < a[start2] ? a[start1] : a[start2]; // while (start1 < end1) // b[k++] = a[start1++]; // while (start2 < end2) // b[k++] = a[start2++]; // } // //交換a和b // int *tmp = a; // a = b; // b = tmp; // } // //若產生交換了 // if (a != data) // { // for (int i = 0; i < n; ++i) // b[i] = a[i]; // b = a; // } // delete b; //} //1趟歸并進程，將兩個有序的子表合成1個新的有序表 void merge(int data[], int low, int mid, int high) { int i = low, j = mid + 1, k = 0; //臨時存儲排好序的數組 int *tmp = new int[high - low + 1]; while (i <= mid && j <= high) { if (data[i] < data[j]) tmp[k++] = data[i++]; else tmp[k++] = data[j++]; } while (i <= mid) tmp[k++] = data[i++]; while (j <= high) tmp[k++] = data[j++]; for (int i = low, k = 0; i <= high; i++, k++) data[i] = tmp[k]; delete tmp; } //遞歸情勢分別對數組的左右兩個子數組歸并排序，然后merge成1個新的有序數組 void mergeSortR(int data[], int low, int high) { int mid; if (low < high) { mid = (low + high) / 2; mergeSortR(data, low, mid); mergeSortR(data, mid + 1, high); merge(data, low, mid, high); } } //自頂向下的2路歸并排序算法 void mergeSort(int data[], int n) { mergeSortR(data, 0, n - 1); } /************************* 9 基數排序 ******************************** 空間復雜度：空間復雜度為O(n) 時間復雜度：最好、最壞、平均的時間復雜度都是O(d(n+r)),其中d是待排序元素的最大位 數，n是元素的個數，r是基數（10進制r=10，2進制r=2）。 穩定性：基數排序是穩定的排序方法 思想：通過"分配"和"搜集"進程實現排序，不需要進行關鍵字之間的比較，是1種借助于多 關鍵字排序的思想對單關鍵字排序的方法，分為最低位優先(LSD）和最高位優(MSD) *******************************************************************/ //輔助函數，求數據的最大位數d int maxbit(int data[], int n) { int d = 1;//保存最大位數，初始為1 int p = 10; for (int i = 0; i < n; ++i) { while (data[i] >= p)
{
p *= 10;//有溢出的風險
++d;
}
}
return d;
}
//基數排序
void radixSort(int data[],int n)
{
//得到最大位數d
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10];//計數器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; ++i) { //清空計數器 for (j = 0; j < 10; ++j) count[j] = 0; for (j = 0; j < n; j++) { k = (data[j] / radix) % 10;//統計每一個桶中的記錄數 count[k]++; } for (j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; for (j = n - 1; j >= 0; j--)
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for (j = 0; j < n; j++) data[j] = tmp[j]; radix = radix * 10; } delete []tmp; delete []count; } void print(int data[], int n) { for (int i = 0; i < n; ++i) cout << data[i] << " "; cout << endl; } //測試 int main() { int data[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy1[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy2[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy3[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy4[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy5[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy6[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy7[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy8[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; int copy9[] = { 3, 6, 1, 5, 0, 4, 2, 9, 8, 7 }; cout << "待排序數組為： "; print(data, sizeof(data) / sizeof(int)); cout << endl << endl; cout << "1 直接插入排序： "; insertSort(copy1, sizeof(copy1) / sizeof(int)); print(copy1, sizeof(copy1) / sizeof(int)); cout << endl; cout << "2 2分插入排序： "; biInsertSort(copy2, sizeof(copy2) / sizeof(int)); print(copy1, sizeof(copy2) / sizeof(int)); cout << endl; cout << "3 希爾排序： "; shellSort(copy3, sizeof(copy3) / sizeof(int)); print(copy1, sizeof(copy3) / sizeof(int)); cout << endl; cout << "4 冒泡排序： "; bubbleSort(copy4, sizeof(copy4) / sizeof(int)); print(copy1, sizeof(copy4) / sizeof(int)); cout << endl; cout << "5 快速排序： "; quickSort(copy5, 0, sizeof(copy5) / sizeof(int)⑴); print(copy1, sizeof(copy5) / sizeof(int)); cout << endl; cout << "6 直接選擇排序： "; selectSort(copy6, sizeof(copy6) / sizeof(int)); print(copy1, sizeof(copy6) / sizeof(int)); cout << endl; cout << "7 堆排序： "; heapSort(copy7, sizeof(copy6) / sizeof(int)); print(copy1, sizeof(copy7) / sizeof(int)); cout << endl; cout << "8 歸并排序： "; mergeSort(copy8, sizeof(copy8) / sizeof(int)); print(copy1, sizeof(copy8) / sizeof(int)); cout << endl; cout << "9 基數排序： "; radixSort(copy9, sizeof(copy9) / sizeof(int)); print(copy1, sizeof(copy9) / sizeof(int)); cout << endl; return 0; }
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
