C - Quick Sort (one of the simplest)-蒲公英云

C - Quick Sort (one of the simplest)

向右看齐 2022-10-23 15:26 246阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

/*
 * Quick Sort:
 *
 * Given an array, one element is chosen and the others partitioned in two subsets
 * - those less than the partition element and those greater than or equal to it.
 * The same process is then applied recursively to the two subsets. When a subset
 * has fewer than two elements, it doesn't need any sorting; this stops the recursion.
 *
 * This version of quicksort is not the fastest possible, but it's one of the simplest.
 * We use the middle element of each subarray for partitioning.
 *
 * QuickSort.c - by FreeMan
 */
 /* QuickSort: Sort v[left]...v[right] into increasing order */
void QuickSort(int v[], int left, int right)
{
    int i, last;
    void Swap(int v[], int i, int j);
    if (left >= right) /* Do nothing if array contains fewer than two elements */
    {
        return;
    }
    Swap(v, left, (left + right) >> 1); /* Move partition element to v[left] */
    last = left;
    for (i = left + 1; i <= right; i++) /* Partition */
    {
        if (v[i] < v[left])
        {
            Swap(v, ++last, i);
        }
    }
    Swap(v, left, last); /* Restore partition element */
    QuickSort(v, left, last - 1);
    QuickSort(v, last + 1, right);
}
/* Swap: Interchange v[i] and v[j] */
void Swap(int v[], int i, int j)
{
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}