void Swap(int* p, int* q)
{
int tmp = *q;
*q = *p;
*p = tmp;
}
//三數取中
int GetMidIndex(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
return mid;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else // a[begin] > a[mid]
{
if (a[mid] > a[end])
return mid;
else if (a[begin] < a[end])
return begin;
else
return end;
}
}
交換函式在多數排序中都會用到，特地寫一個交換函式比較方便，
插入排序
思路：插入排序基本操作就是將一個資料插入到已經排序好的有序序列中，從而得到一個新增一個資料的序列；
// 插入排序
void InsertSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
//a[end+1] = a[end];
Swap(&a[end], &a[end + 1]);
--end;
}
else
{
break;
}
}
//a[end + 1] = tmp;
}
return a;
}
希爾排序
在希爾排序里我們首先會設定一個增量值 ，然后把資料按照增量分為幾組（分組只是邏輯上的分組并非真的分組） 然后對分組內的資料進行排序，排序完成后 增量變小，然后再根據增量進行排序，依次類推 當增量為1時，再進行排序的時候，此時的資料經過前幾次的處理，變得相對很規律，
// 希爾排序
void ShellSort(int* a, int n)
{
assert(a);
int gap = n;
while (gap > 1)
{
//確保最后一次時gap為1；
//gap逐漸縮小；
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
//a[end+1] = a[end];
Swap(&a[end], &a[end + gap]);
end -= gap;
}
else
{
break;
}
}
//a[end + 1] = tmp;
}
}
return a;
}
選擇排序
選擇排序是在一組資料中找到最小的數之后，將其與第一個數交換，第一個數就變的有序，然后再從第二個數開始遍歷，找到最小的數，與第二個數交換，以此類推；
在這里對其進行優化：同時找到最大的數和最小的數，放到最后一位和第一位，以此類推；
//選擇排序
void SelectSort(int* a, int n)
{
assert(a);
int end = n - 1, begin = 0;
while (begin < end)
{
int min,max;//最大數和最小數的下標
min = max = begin;
//回圈找到最大的數和最小的數
for (int i = begin+1; i <= end; i++)
{
if (a[i] > a[max])
{
max = i;
}
if (a[i] < a[min])
{
min = i;
}
}
Swap(&a[begin], &a[min]);
//防止第一個元素為max，若第一個元素最大，此時min下標為第一個，先讓max=min；
if (begin == max)
{
max = min;
}
Swap(&a[end], &a[max]);
//縮小范圍
begin++; end--;
}
}
冒泡排序
將相鄰元素兩兩比較，反序則交換，每一趟都將最大的數交換到最后面；
//冒泡排序
void BubbleSort(int* a, int n)
{
assert(a);
for (int i = 0; i < n-1; i++)
{
for (int j = 0; j < n-i-1; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
return a;
}
zhi## 快速排序（三種方法）
一共三種方法，都是設定一個基準數，把比基準數大的數放到后面，把比基準數小的數放到前面，再進行遞回，使其有序
一、左右指標法
一前一后兩個指標，right從最后面出發，left從最前面出發，left找到比key（key即為基準值）大的之后，right再往前走找到比key小的，兩數交換，以此類推，最后key恰好落到最終排序后的位置上，然后在key前后兩個區間遞回；
// 快速排序左右指標法
int PartSort1(int* a, int left, int right)
{
//int key = a[right];
//三數取中，防止逆序時為時間復雜度最大；
int midIndex = GetMidIndex(a, left, right);
Swap(&a[midIndex], &a[right]);
int keyi = right;
while (right > left)
{
while (right > left && a[left] <= a[keyi]) left++;
while (right > left && a[right] >= a[keyi]) right--;
Swap(&a[right], &a[left]);
}
Swap(&a[keyi], &a[right]);
return left;
}
void QuickSort1(int* a, int left, int right)
{
assert(a);
if (left >= right) return;
int meet = PartSort1(a, left, right);
QuickSort1(a, left, meet - 1);
QuickSort1(a, meet + 1, right);
return a;
}
二、挖坑法
先將key保存，將key的位置作為坑的位置，left先找到一個比key大的數，將其填入key的位置，left的位置變成坑，right再找到一個比可以key小的數，然后填入坑，以此類推，最后key恰好落到最終排序后的位置上，然后在key前后兩個區間遞回；
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
int midIndex = GetMidIndex(a, left, right);
Swap(&a[midIndex], &a[right]);
int key = a[right];
while (right > left)
{
while (right > left && a[left] <= key) left++;
a[right] = a[left];
while (right > left && a[right] >= key) right--;
a[left] = a[right];
}
a[left] = key;
return left;
}
void QuickSort2(int* a, int left, int right)
{
assert(a);
if (left >= right) return;
int meet = PartSort2(a, left, right);
QuickSort2(a, left, meet - 1);
QuickSort2(a, meet + 1, right);
return a;
}
三、前后指標法
一前一后兩個指標，初始cur=0，prev=cur-1，cur像是火車頭，拉著比key值大的數往最后面走；
// 快速排序前后指標法
int PartSort3(int* a, int left, int right)
{
int midIndex = GetMidIndex(a, left, right);
Swap(&a[midIndex], &a[right]);
int prev = left - 1;
int cur = left;
int keyindex = right;
while (cur < right)
{
if (a[cur] < a[keyindex] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[++prev], &a[keyindex]);
return prev;
}
void QuickSort3(int* a, int left, int right)
{
assert(a);
if (left >= right) return;
int meet = PartSort1(a, left, right);
QuickSort3(a, left, meet - 1);
QuickSort3(a, meet + 1, right);
return a;
}
歸并排序
遞回實作：
歸并排序是利用歸并的思想實作的排序演算法，該演算法采用經典的分治策略（分治法將問題分成一些小的問題然后遞回求解，而治的階段則將分的階段得到的各答案‘修補’在一起，即分而治之），
// 歸并排序遞回實作
void _MergeSort(int* a, int L,int R,int* tmp)
{
if (L >= R)
return;
int M = (L + R) / 2;
_MergeSort(a, L, M, tmp);
_MergeSort(a, M + 1, R, tmp);
int begin1 = L, end1 = M;
int begin2 = M + 1, end2 = R;
int i = L;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
tmp[i++] = a[begin2++];
else
tmp[i++] = a[begin1++];
}
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
for (int i = L; i <= R; i++)
{
a[i] = tmp[i];
}
}
void MergeSort(int* a, int n)
{
assert(a);
int* tmp = malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
return a;
free(tmp);
}
// 歸并排序非遞回實作
void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)
{
int left = begin1, right = end2;
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
tmp[index++] = a[begin1++];
else
tmp[index++] = a[begin2++];
}
while (begin1 <= end1)
tmp[index++] = a[begin1++];
while (begin2 <= end2)
tmp[index++] = a[begin2++];
// 把歸并好的再tmp的資料在拷貝回到原陣列
for (int i = left; i <= right; ++i)
a[i] = tmp[i];
}
void MergeSortNonR(int* a, int n)
{
assert(a);
int* tmp = malloc(sizeof(int) * n);
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [i,i+gap-1] [i+gap, i+2*gap-1]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 1、合并時只有第一組,第二組不存在，就不需要合并
if (begin2 >= n)
break;
// 2、合并時第二組只有部分資料，需要修正end2邊界
if (end2 >= n)
end2 = n - 1;
MergeArr(a, begin1, end1, begin2, end2, tmp);
}
//PrintArray(a, n);
gap *= 2;
}
free(tmp);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/253517.html
標籤：其他