快速排序

简介: 快速排序。

在区间中随机挑选一个元素作基准,将小于基准的元素放在基准之前,大于基准的元素放在基准之后,再分别对小数区与大数区进行排序。
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等於負值時引發段錯誤(Segment Fault)
// 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.start + range.end) / 2]; // 選取中間點為基準點
int left = range.start, right = range.end;
do
{
while (arr[left] < mid) ++left; // 檢測基準點左側是否符合要求
while (arr[right] > mid) --right; //檢測基準點右側是否符合要求

        if (left <= right)
        {
            swap(&arr[left],&arr[right]);
            left++;right--;               // 移動指針以繼續
        }
    } while (left <= right);

    if (range.start < right) r[p++] = new_Range(range.start, right);
    if (range.end > left) r[p++] = new_Range(left, range.end);
}

}

相关文章
快速排序(超超详细,因为自己也不是很会)
快速排序(超超详细,因为自己也不是很会)
|
6月前
|
搜索推荐 C++
C++快速排序的实现
C++快速排序的实现
|
6月前
|
算法
快速排序(三)——hoare法
快速排序(三)——hoare法
68 1
快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
33 0
|
算法 搜索推荐
快速排序到底有多快
快速排序到底有多快
86 0
重新理解快速排序
重新理解快速排序
54 0
|
C语言
快速排序就这么简单
从前面已经讲解了冒泡排序、选择排序、插入排序了,本章主要讲解的是快速排序,希望大家看完能够理解并手写出快速排序的代码,然后就通过面试了!如果我写得有错误的地方也请大家在评论下指出。
132 0
快速排序就这么简单
3 背包问题及其衍生
3 背包问题及其衍生
70 0