快速排序c实现（代码来自c programming language)

最新推荐文章于 2025-03-17 17:58:34 发布

overstack

最新推荐文章于 2025-03-17 17:58:34 发布

阅读量713

点赞数

分类专栏： c++/c

本文链接：https://blog.csdn.net/overstack/article/details/8457689

版权

c++/c 专栏收录该内容

30 篇文章

订阅专栏

Our version of quick sort is not the fastest possible, but it's one of the simplest. We use the middle element of each sub array for partitioning.

#include <cstdio>

void swap(int a[], int left, int right)
{
    int tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
}

void qsort(int a[], int left, int right)
{
    if (left >= right) // do nothing if array contains fewer
        return;        // than two elements
    
    int i,last;
    
    swap(a, left, (left+right)/2); // move partition elem to a[0]
    last = left;
    for (i = left+1; i <= right; i++) // partition
    {   
        if (a[i] < a[left])
        {   
            swap(a, ++last, i); 
        }   
    }   
    swap(a, last, left);  // restore partition elem

    qsort(a, left, last-1);
    qsort(a, last+1, right);
}

int main()
{
    int a[] = {1, 3, 2, 5, 34, 23, 1, 0}; 
    int size = sizeof(a) / sizeof(a[0]);
    qsort(a, 0, size-1);
    for (int i = 0; i < size; i++)
        printf("%d  ", a[i]);
    printf("\n");
    return 0;
}