快速排序
本文最后更新于 2717 天前,其中的信息可能已经有所发展或是发生改变。

内容纲要

[hide][code lang=”c”]//迭代法

typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; //避免len等於負值時宣告堆疊陣列當機
//r[]模擬堆疊,p為數量,r[p++]為push,r[–p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = new_Range(0, len – 1);
while (p) {
Range range = r[–p];
if (range.start >= range.end)
continue;
int mid = arr[range.end];
int left = range.start, right = range.end – 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right–;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[range.end])
swap(&arr[left], &arr[range.end]);
else
left++;
r[p++] = new_Range(range.start, left – 1);
r[p++] = new_Range(left + 1, range.end);
}
}
//遞歸法

void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;//這是為了防止宣告堆疊陣列時當機
int mid = arr[end];
int left = start, right = end – 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right–;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left) {
quick_sort_recursive(arr, start, left – 1);
quick_sort_recursive(arr, left + 1, end);
} else {
quick_sort_recursive(arr, left + 1, end);
}
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len – 1);
}
[/code][/hide]

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇