快速排序
1.hoare版本
根據(jù)動圖的演示，整理的思路如下，
1.定義left,right,key。key默認是左邊第一個元素，像兩個指針，左邊找比key大的，右邊找比k小的，找到的話，交換二者，往返這個過程，當left與right相遇時，交換key和此時相遇的值.
#include<stdio.h>
void swap(int*p,int*q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
int PartSort1(int* a, int left, int right)
{
int keyi =left;
while (left < right)
{
while (left<right && a[right]>=a[keyi])
{
right--;
}
while (left<right && a[left]<= a[keyi])
{
left++;
}
swap(&a[left],&a[right]);
}
swap(&a[keyi], &a[left]);
return left;
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
PartSort1(arr, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}
單趟下來，6出現(xiàn)在正確的位置。
1.為什么大循環(huán)是left<right?
當兩個小人走到一塊去的時候，我們應(yīng)該交換key位置的值，和相遇時候的值了，而不是讓他們兩個岔開.
2.為什么在小循環(huán)中要加left<right?
假如說數(shù)組是10,10,10,10,10,10,10,10,10
在小循環(huán)中一直找小，找不到就會越界.
3.return的值有什么用？
return的值相當于分了界，然后就可以分別對子區(qū)間使用快排了.
針對每個子區(qū)間，使用快排
#include<stdio.h>
void swap(int*p,int*q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
int PartSort1(int* a, int left, int right)
{
int keyi =left;
while (left < right)
{
while (left<right && a[right]>=a[keyi])
{
right--;
}
while (left<right && a[left]<= a[keyi])
{
left++;
}
swap(&a[left],&a[right]);
}
swap(&a[keyi], &a[left]);
return left;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int mid=PartSort1(a,begin,end);
QuickSort(a,begin, mid - 1);
QuickSort(a,mid+1,end);
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(arr, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}
遞歸結(jié)束條件，如果有兩個數(shù)據(jù)的話還能排一次，如果只有一個數(shù)據(jù)的話就不用排了
1.為什么要右邊先走，左邊再走，為啥相遇的值一定比key小或者等于key？
情況1：右邊找小，找不到小，一直往左走，與key碰面，相遇的值為key;
情況2：右邊找到了小，停在那里，左邊找大，一直找不到大，相遇點就停在了比key小的那里
情況3：交換值之后，右邊一直找不到小，一直走，相遇點就是左邊剛交換完，還沒有動的比key小的值.
情況4：交換值之后，右邊繼續(xù)移動，找到小停在那，左邊找不到大，相遇點就是比key小的.
2.挖坑法
1.創(chuàng)建臨時變量key保存最左側(cè)坑位的值，右邊找小找到小之后，將找到的小值填到左邊的坑位去，這里變成坑位.左邊找大，找到大之后，將該值填入右側(cè)的坑位，依次循環(huán)，相遇之后，將key放到相遇點
#include<stdio.h>
void swap(int*p,int*q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int pole = left;
while (left < right)
{
while (left < right && a[right] >=key)
{
right--;
}
a[pole] = a[right];
pole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[pole] = a[left];
pole = left;
}
a[left] = key;
return left;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int mid=PartSort2(a,begin,end);
QuickSort(a,begin, mid - 1);
QuickSort(a,mid+1,end);
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(arr, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}
3.前后指針法
前后指針法
#include<stdio.h>
void swap(int*p,int*q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int cur = left + 1;
int prev = left;
while (cur<=right)
{
if (a[cur] < a[keyi])
{
prev++;
swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[keyi], &a[prev]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int mid=PartSort3(a,begin,end);
QuickSort(a,begin, mid - 1);
QuickSort(a,mid+1,end);
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(arr, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
}
4.快速排序非遞歸版
采用非遞歸代替遞歸分割步驟，當區(qū)間只有一個值時，將不在入棧.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void swap(int*p,int*q)
{
int tmp = *p;
*p = *q;
*q = tmp;
}
typedef struct Stack//定義一個棧的結(jié)構(gòu)體變量
{
int* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
assert(ps);//斷言，防止為空指針
ps->a = NULL;//所指向的地址為空
ps->capacity = ps->top = 0;//容量和棧中元素個數(shù)均為0
}
void StackPush(Stack* ps, int data)
{
assert(ps);
if (ps->capacity == ps->top)//如果棧中的元素個數(shù)等于棧的容量時考慮擴容，
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果剛開始時都等于0，就先給4個空間大小，后面如果滿的話，容量擴大1倍
int* newnode = (int*)realloc(ps->a, sizeof(int) * newcapcity);//申請空間，將申請好的空間首地址傳給newnode指針
assert(newnode);//斷言，防止malloc失敗
ps->a = newnode;//將newnode保存的申請空間的首地址傳給ps->a,讓ps->a指向創(chuàng)建好的空間
ps->capacity = newcapcity;//容量大小更新為新容量大小
}
ps->a[ps->top] = data;//像存數(shù)組一樣存數(shù)據(jù)
ps->top++;//指向下一個
}
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;//ps->top為棧中元素個數(shù).==0棧中無元素，無元素要返回1， 無元素ps->t0p==0，這個表達式結(jié)果是1，返回1;
}
// 出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//防止棧內(nèi)無元素，繼續(xù)出棧
ps->top--;
}
// 獲取棧頂元素
int StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];//ps->top為棧中元素個數(shù)，由于數(shù)組下標是從0開始，所以棧頂元素下標為ps->top-1;
}
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
// 銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);//free掉動態(tài)申請的內(nèi)存
ps->a = NULL;//防止野指針
ps->capacity = ps->top = 0;//容量和棧中元素個數(shù)置為0
}
int PartSort1(int* a, int left, int right)
{
int keyi =left;
while (left < right)
{
while (left<right && a[right]>=a[keyi])
{
right--;
}
while (left<right && a[left]<= a[keyi])
{
left++;
}
swap(&a[left],&a[right]);
}
swap(&a[keyi], &a[left]);
return left;
}
void QuickSort(int* a, int begin, int end)
{
Stack st;
StackInit(&st);
StackPush(&st,end);
StackPush(&st,begin);
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int mid = PartSort1(a, left, right);
if (mid + 1 < right)
{
StackPush(&st,right);
StackPush(&st,mid+1);
}
if (left < mid-1)
{
StackPush(&st,mid-1);
StackPush(&st,left);
}
}
StackDestroy(&st);
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
QuickSort(arr, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
}
歸并排序
基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<string.h>
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
_MergeSort(a, begin,mid, tmp);
_MergeSort(a, mid+1, end, tmp);
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int j = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
if (a[begin2] < a[begin1])
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//歸并排序
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
MergeSort(arr, 10);
for (int i = 0; i < 10; i++)
{
printf("%d ",arr[i]);
}
}
0-0,1-1return回0-1，
2-2return回0-2
歸并排序非遞歸版
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
}
int gap = 1;
while (gap<n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
if (a[begin2] < a[begin1])
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5 };
MergeSortNonR(arr, 8);
for (int i = 0; i < 8; i++)
{
printf("%d ",arr[i]);
}
}
gap=1，兩個兩個排序，然后整體拷貝回去.
gap=2,四個四個排序，然后整體拷貝回去.
gap=8 八個排序，然后整體拷貝回去.
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10 };
MergeSortNonR(arr, 9);
for (int i = 0; i < 9; i++)
{
printf("%d ",arr[i]);
}
}
我們換成9個數(shù)據(jù)，發(fā)現(xiàn)程序崩潰.
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
}
int gap = 1;
while (gap<n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
printf("gap=%d [%d,%d][%d,%d]\n",gap, begin1, end1, begin2, end2);
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
if (a[begin2] < a[begin1])
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
}
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;
}
}
修正邊界文章來源：http://www.zghlxwxcb.cn/news/detail-808735.html
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
}
int gap = 1;
while (gap<n)
{
int j = 0;
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i;
int end1 = i + gap - 1;
int begin2 = i + gap;
int end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
if (a[begin2] < a[begin1])
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
}
int main()
{
int arr[] = { 6,1,2,7,9,3,4,5,10 };
MergeSortNonR(arr, 9);
for (int i = 0; i < 9; i++)
{
printf("%d ",arr[i]);
}
}
1.修改邊界后往回拷貝的就不是n了，而是這個end2 - i + 1
2.如果是9個數(shù)據(jù)的時候，最后一個數(shù)據(jù)在gap=8中才開始排序
文章來源地址http://www.zghlxwxcb.cn/news/detail-808735.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】快速排序，歸并排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
