快速排序在實際應用中是比較表現好的排序算法。快速排序我用兩種方法實作它。
第一種為方法,形象的稱為:挖坑法
基本思路:1、尋找pos位,然後将其分為兩段數組,然後對這兩段數組遞歸排序;
2、指定一個基數temp(三數取中法),定義兩個指針begin一個指向起始位置,end一個指向最後一個元素的位置。begin尋找比基數(temp)大的數字,找到 後将begin的資料賦給end,begin成為一個坑,然後end尋找比基數(temp)小的數字,找到将end的資料賦給begin,end成為一個新坑,循環這個過程,直到begin指針與end指針相遇,然後将temp的資料傳回給那個坑,然後進行遞歸操作。
代碼實作為:
int PastSort1(int *arr, int left, int right) //挖坑法
{
int begin = left;
int end = right;
int temp = arr[mid(arr,left,right)];
while (begin < end)
{
while (begin < end && arr[begin] <= temp)
begin++;
if (begin < end)
arr[end] = arr[begin];//begin成為新坑
while (begin < end && arr[end] >= temp)
end--;
if (begin < end)
arr[begin] = arr[end]; //end成為新坑
}
arr[begin] = temp; //将temp填補進去
return begin;
}
void QuickSort(int *arr,int left,int right)
{
if (arr == NULL || left > right)
return;
int pos = PastSort1(arr, left, right);
QuickSort(arr, left, pos - 1);
QuickSort(arr, pos + 1, right);
}
前後指針法:
定義兩個指針,一前一後,前面指針找比基數小的數,後面指針找比基數大的數,前面的指針找到後,将前後指針所指向的資料交換,目前面的指針周遊完整個數組時,将基數值與後指針的後一個位置的資料進行交換,然後以後指針的後一個位置作為分界,然後将數組分開,進行遞歸排序。
代碼實作:
int PastSort2(int* arr, int left, int right) //前後指針法
{
int cur = left; //找小
int ptr = left-1;//找大
int temp = arr[mid(arr, left, right)];
while (cur < right)
{
if (arr[cur] < temp)
{
swap(arr[cur], arr[++ptr]);
}
cur++;
}
swap(arr[++ptr], arr[right]);
return ptr;
}
void QuickSort(int *arr,int left,int right)
{
if (arr == NULL || left > right)
return;
int pos = PastSort2(arr, left, right);
QuickSort(arr, left, pos - 1);
QuickSort(arr, pos + 1, right);
}
基數排序:
基本原理是:
代碼實作為:
int getbit(int* arr,int size) //獲得最大位數
{
int bits = 1;
int rang = 10;
for (int i = 0; i < size; ++i)
{
while (arr[i] >= rang)
{
++bits;
rang *= 10;
}
}
return bits;
}
void BucketSort(int* arr, int size)
{
int bits = getbit(arr, size);
int radix = 1;
int count[10];
for (int bit = 1; bit <= bits;bit++) //循環最大位數次
{
memset(count, 0, sizeof(int)* 10);
for (int i = 0; i < size; ++i)//統計數字位數的數量
{
int index = (arr[i] / radix) % 10;
count[index]++;
}
for (int j = 1; j < 10; j++) //固定數值排序的位置
{
count[j] = count[j] + count[j - 1];
}
int *str = new int[size];
memset(str, 0, sizeof(int)*size);
for (int i = size-1; i >=0; i--)//按照固定的位置将資料寫入輔助數組
{
int index = (arr[i] / radix) % 10;
str[count[index]-1] = arr[i];
count[index]--;
}
radix = radix * 10;
for (int i = 0; i < size; i++) //将輔助數組中的數拷貝回原數組
{
arr[i] = str[i];
}
delete[] str;
}
}
前面我用了三篇文章來寫幾種常見的排序方法,我用一個圖簡單分析一下他們的最好最壞平均時間複雜度,以及空間複雜度,與穩定性分析。