排序
1. 在多個數據元素（Ri）的序列，其中每個元素有相應的關鍵字(Ki)（也叫元素的屬性），通過關鍵字的固有關系來對對應數據元素進行排序
2. 排序穩定性：元素R1 R2 的關鍵字K1 K2相同，排序前R1在R2前面，排序后 R1在R2前面，則該排序方法是穩定的。
3. 多關鍵字排序：排序先用最高優先級的關鍵字N1進行排序，，當N1關鍵字相同時使用N2優先級關鍵字進行排序，如果關鍵字還是相同依次使用N2，，Nn-1
4. 排序和交換兩個重要手段
5. 排序選擇要素：時間性能，空間性能，程序復雜度
1.選擇排序
思想：在排序到當前序列第 i 和元素時，從后面 n-i 個元素中選出最小元素，作為當前排序序列第 i 個元素。
code:
static void select(T array[], int len) { for(int x = 0; x < len; x++) { int min = x; for(int y = x + 1; y < len; y++) { if(array[min] > array[y]) //升序< 降序> min = y; } if(min != x) swap(array[x],array[min]); //不穩定排序 }
2.插入排序
思想：序列分為有序序列和無需序列。未排序序列選擇第 i (1) 位的元素時，插入到前面的有序序列，使用 i 元素的關鍵字與前 i-1 個元素關鍵字進行比較，找到位置后插入即可
template <typename T>
static void insert_sort(T array[], int len, bool ascend = false)
{
for(int x = 1; x < len; x++)
{
int z = x;
T temp = array[z];
for(int y = x - 1; (y >= 0) && (ascend ? array[y] > temp: array[y] < temp); y--)
{
array[y + 1] = array[y]; //穩定排序
z = y;
}
if(z != x)
{
array[z] = temp;
}
}
}
3.冒泡排序
思想：序列分為有序序列和無序序列，從整個序列的最后一個元素開始向前依次比較大小，小則比較數前移，大則用被比較的元素前移。
template <typename T>
static void bubble_sort(T array[], int len, bool ascend = false)
{
bool state = ture;
for(int x = 0; x < len && state; x++) //某個元素無法前的元素都是有序的，表明有序
{
state = false;
for(int y = len - 1; y > x; y--)
{
if(ascend ? array[y] > array[y - 1] : array[y] < array[y - 1])
{
swap(array[y],array[y - 1]);
state = ture;
}
}
}
}
4.希爾排序
思想：將n個元素的序列分為d組，每一組使用插入排序。然后再分為d-1組，再分別排序。直到d=1。
如何分組： 將n個元素分為d個子序列：第一組：{R[1],R[1+d],R[1+2d]...R[1+kd]} 第二組：{R[2],R[2+d],R[2+2d]....R[2+kd]} .........第d組：{R[d],R[2d],R[3d]...R[(1+k)d]} 。
template <typename T>
static void shell_sort(T array[], int len, bool ascend = false)
{
int d = len;
do
{
d = d / 3 + 1; //???
for(int x = d ; x < len; x += d)
{
int z = x;
T temp = array[z];
for(int y = x - d; (y >= 0) && (ascend ? array[y] > temp: array[y] < temp); y -= d)
{
array[y + d] = array[y]; //穩定排序
z = y;
}
if(z != x)
{
array[z] = temp;
}
}
}
while(d > 1);
}
5.歸并排序
思想：先將一個無序序列劃分為兩個無序序列，再將兩個無序序列接著向下劃分，直到每個子序列只包含一個元素此時每個子序列都是有序序列，
再兩個兩個子序列比較后合并，直到所有子序列合并為原來的序列，此時序列變為有序。
幾個有序序列歸并就叫幾路歸并。
穩定但是花費空間
template <typename T>
static void merge_sort(T array[], int len, bool ascned = ture)
{
T* temp_array = new T[len];
merge_sort_core(array, temp_array, 0, len - 1, ture);
delete[] temp_array;
}
template <typename T>
static void merge_sort_core(T array[], T temp_array[], int begin, int end, bool ascned = ture)
{
if(begin == end)
{
return;
}
else
{
// 分割
int mid = (begin + end) / 2;
merge_sort_core(array, temp_array, begin, mid, ascned);
merge_sort_core(array, temp_array, mid + 1, end, ascned);
// 合并
int x = begin, y = mid + 1, z = begin;
while(x <= mid && y <= end)
{
if(array[x] < array[y])
{
temp_array[z++] = array[x++];
}
else
{
temp_array[z++] = array[y++];
}
}
while(x <= mid)
{
temp_array[z++] = array[x++];
}
while(y <= end)
{
temp_array[z++] = array[y++];
}
for(z = begin; z <= end; z++)
{
array[z] = temp_array[z];
}
}
}
6.快速排序
思想： 通過在序列中選擇一個基準值對一個無序序列劃分，將無序序列大于基準值的放在左邊，小于基準值的放在右邊。再把左右兩個子序列繼續尋找基準值繼續劃分下去。
最后每個序列都只有一個元素，而此時整個序列變成有序的。
不穩定但是花費空間
template <typename T>
static void quick_sort(T array[], int len, bool ascned = ture)
{
quick_sort_core(array, 0, len - 1, ascned);
}
template <typename T>
static void quick_sort_core(T array[], int begin, int end, bool ascned = ture)
{
//確定基準值的位置
int base_pos = 0, base_value = array[begin], begin_slide = begin, end_slide = end;
while(begin_slide < end_slide)
{
while(begin_slide < end_slide && ascned ? base_value < array[end_slide] : base_value > array[end_slide])
{
--end_slide;
}
swap(array[begin_slide], array[end_slide]);
while(begin_slide < end_slide && ascned ? base_value >= array[begin_slide] : base_value <= array[begin_slide])
{
++begin_slide;
}
swap(array[begin_slide], array[end_slide]);
}
array[begin_slide] = base_value;
base_pos = begin_slide;
//繼續劃分
quick_sort_core(array, begin, (base_pos - 1), ascned);
quick_sort_core(array, base_pos + 1, end, ascned);
}
浙公網安備 33010602011771號