1. 插入排序
1. 直接插入排序
void XYInsertSort::sorted(int *arr)
{
int sentry;
for (int i = 1; i < arrCount; i++) {
sentry = arr[i];
int j = i - 1;
for (j = i - 1; j >= 0; j--) {
if (sentry < arr[j]) {
arr[j + 1] = arr[j];
}else{
break;
}
}
arr[j + 1] = sentry;
}
}
最好情況：順序 T = O(n)
最壞情況：逆序 T = O(n2)
直接插入排序算法簡便，當待排數(shù)據(jù)數(shù)量n很小時，這是一個很好的排序方法。但是通常待排數(shù)據(jù)數(shù)量n很大。因此直接插入排序就不適用了。
2. 折半插入排序
- 由于插入排序是在一個有序的數(shù)據(jù)中查找和插入，因此我們可以用折半比較的方式確定插入位置。
void XYBInsertSort::sorted(int *arr)
{
int sentry, low, height, mid;
for (int i = 1; i < arrCount; i++) {
sentry = arr[i];
low = 0;
height = i - 1;
while (low <= height) {
mid = (low + height) / 2;
if (sentry < arr[mid]) {
height = mid - 1;
}else if (sentry > arr[mid]){
low = mid + 1;
}else{
low = mid + 1;
break;
}
}
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = sentry;
}
}
折半插入排序僅減少了關鍵字間的比較次數(shù)，而記錄移動次數(shù)不變，因此，折半插入排序的時間復雜度仍為O(n2)。
3. 2-路插入排序
?? 2-路插入排序在折半插入排序的基礎上再改進之，其目的是減少排序過程中的移動次數(shù)，但需要添加n的輔助空間。我們添加一個數(shù)組arrB,并將其看做循環(huán)鏈表，并設置兩個指針first和fianl分別指向第一個記錄和最后一個記錄。
?? 先拿arrA中的元素跟arrB[first]進行比較,如果小于arrB[first]，則插入到arrB[first]前面。否則再與arrB[final]比較，如果大于arrB[final]出入到其后面。否則，直接插入法插入到first和final中間的位置。
//二路插入排序
void XYTwInsertSort::sorted(int *arr)
{
int *arrB = (int*)malloc(sizeof(int) * arrCount);
arrB[0] = arr[0];
int first = 0, last = 0;
for (int i = 1; i < arrCount; i++) {
if(arr[i] < arrB[first])
{
first = (first - 1 + arrCount) % arrCount;
arrB[first] = arr[i];
}else if (arr[i] > arrB[last]){
last++;
arrB[last] = arr[i];
}else{
last++;
arrB[last] = arrB[last - 1];
int j = last - 1;
for(;arr[i] < arrB[(j - 1 + arrCount) % arrCount]; j = (j - 1 + arrCount) % arrCount){
arrB[j] = arrB[(j - 1 + arrCount) % arrCount];
}
arrB[j] = arr[i];
}
}
for (int k = 0; k < arrCount; k++) {
arr[k] = arrB[first];
first = (first + 1) % arrCount;
}
}
4. 表插入排序
理解了之前的2-路插入排序算法之后，再此詳解表插入排序:折半插入排序相比于直接插入排序減少了比較的次數(shù);·2-路插入排序相比于折半插入排序減少了移動的次數(shù);
- 表插入排序則是在排序過程中不移動記錄，只改變存儲結構，進行表插入排序的過程;
- 具體做法:使用靜態(tài)鏈表類型作為待排記錄序列的存儲結構，并且設置數(shù)組下標為0的分量為頭結點。
- 第一步:將靜態(tài)鏈表中數(shù)組下標為1的分量和表頭節(jié)點構成一個循環(huán)鏈表，然后依次將下標為2到n的分量按記錄的關鍵字非遞減有序插入到循環(huán)鏈表中。
void XYTableInsertSort::sorted(int *arr)
{
table[0].next = 1;
//當前位置
int index;
//前驅
int pre;
for (int i = 2; i < arrCount + 1; i++) {
index = table[0].next;
pre = 0;
while (index!=0 && table[i].data >= table[index].data) {
pre = index;
index = table[index].next;
}
//當?shù)竭_表尾或table[i].data < table[index].data時，插入到index之前
table[i].next = index;
//修改前驅的指向
table[pre].next = i;
}
//遍歷表存入到num_p數(shù)組中
int curTableIndex = table[0].next;
for(int i = 0; i< arrCount; i++)
{
arr[i] = table[curTableIndex].data;
curTableIndex = table[curTableIndex].next;
}
}
- 從表插入排序的過程可以看到，表插入排序的基本操作還是將一個記錄插入到已排好序的有序表中;
- 表插入排序和直接插入排序相比，不同之處是僅以修改2n次指針代替記錄的移動，排序過程中所需進行的關鍵字之間的比較次數(shù)相同，所以表插入排序的時間復雜度是O(n2);
- 表插入排序的結果只是求得一個有序鏈表(靜態(tài))，則只能對進行順序查找，而不能進行隨機查找，如果要實現(xiàn)折半之類的查找，則需要對記錄進行重排。
2. 希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。
?? 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。
void XYShellSort::sorted(int *arr)
{
int dk = arrCount / 2 + 1;
int sentry;
while (dk > 0) {
for (int i = dk; i < arrCount; i++) {
sentry = arr[i];
int j;
for ( j = i - dk; j >= 0; j -= dk) {
if (sentry < arr[j]) {
arr[j + dk] = arr[j];
}else{
break;
}
}
arr[j + dk] = sentry;
}
dk /= 2;
}
}
- 希爾排序是基于插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間的時間復雜度為O(n3/2)，希爾排序時間復雜度的下界是n*log2n
3. 快速排序
1. 冒泡排序
int * XYBubblingSort::sorted(int *arr)
{
for (int i = 0; i < arrCount - 1; i++) {
for (int j = 0; j < arrCount - 1 - i ; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
- 冒泡排序的時間復雜度為T = O(n2)
冒泡排序的優(yōu)化
當某趟比較不再交換時，說明已經(jīng)有序，就沒必要繼續(xù)比較了。
int * XYBubblingSort::sorted2(int *arr)
{
for (int i = 0; i < arrCount - 1; i++) {
bool flag = true;
for (int j = 0; j < arrCount - 1 - i ; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
if(flag)
break;
}
return arr;
}
快速排序(Quick Sort):是對冒泡排序的一種改進。它的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可以分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。
void XYQuickSort::sorted(int *arr, int low, int height)
{
if (low < height) {
int pivotloc= partition(arr, low, height);
sorted(arr, low, pivotloc - 1);
sorted(arr, pivotloc + 1, height);
}
}
int XYQuickSort::partition(int *arr, int low, int height)
{
int sentry = arr[low], temp;
while (low < height) {
while (low < height && sentry <= arr[height]) {
height--;
}
temp = arr[height];
arr[height] = sentry;
arr[low] = temp;
while (low < height && sentry >= arr[low]) {
low++;
}
temp = arr[low];
arr[low] = sentry;
arr[height] = temp;
}
return low;
}
- 快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n2)。
4. 選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
void XYSelectSort::sorted(int *arr)
{
int min, minIndex, temp;
for (int i = 0; i < arrCount - 1; i++) {
min = arr[i];
minIndex = i;
for (int j = i + 1; j < arrCount; j++) {
if (arr[j] < min ) {
min = arr[j];
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
5. 堆排序
- 咱們前面已經(jīng)講解了堆，堆排序的方法是刪除堆返回最大堆的最大值或最小堆的最小值，從而實現(xiàn)堆排序。
- 堆排序的時間復雜度 T = O(nlogn)
最大堆排序
void MaxHeapSort(MaxHeap h)
{
printf("堆排序：");
for (int i = 1; i <= h->capacity; i++) {
ElementType item = deleteMax(h);
printf("%d ",item);
}
}
