首页 > 代码库 > 排序算法之快速排序

排序算法之快速排序

2024-09-30 23:33:39   204人阅读

思路：快速排序也是利用了分治算法。总体是，首先在将要比较的数组中找到一个基准，然后用该基准和数组中的剩余元素进行比较，小于该基准的就放到该基准的左侧，大于该基准的就放到右侧，紧接着再对左右两侧的数组再进行快速排序，依次逐渐递归，最后生成的数组就是有序数组。

图片引用网址 ：http://www.cnblogs.com/MOBIN/p/4681369.html

　　　　　　技术分享

 

/*
 * quickSort.cpp
 *
 *  Created on: 2017年6月4日
 *      Author: MrZhang
 */

#include <iostream>
using namespace std;

template <typename T >
int partition( T arr[], int iLeft, int iRight )
{
    T pivot = arr[iLeft];
    int L = iLeft, R = iRight;  //初始化时，L指向第一个坑。

    while( L < R )
    {
        while( arr[R] >= pivot && R > L )  //直到由此留由一个坑，才能进行下面的循环
        {
            R--;
        }
        arr[L] = arr[R];

        while( arr[L] <= pivot && L < R )
        {
            L++;
        }
        arr[R] = arr[L];
    }
    arr[L] = pivot;
    return L;
}

template < typename T >
void __quickSort( T arr[], int iLeft, int iRight )
{
    if( iLeft >= iRight )
    {
        return;
    }
    int p = partition(arr, iLeft, iRight );
    __quickSort( arr, iLeft, p - 1 );
    __quickSort( arr, p + 1, iRight );
}

template < typename T >
void quickSort( T arr[], int iMaxNum )
{
    __quickSort( arr, 0, iMaxNum -1 );
}

int main( )
{
    //setbuf(stdout,NULL);
    unsigned int pucBuff[10] = {3,4,1,7,3,7,8,9,4,0};
    cout << "排序前\n" << endl;
    for( unsigned int i = 0; i < sizeof(pucBuff)/sizeof(int); i++ )
    {
        cout << pucBuff[i] << " " ;
    }
    cout << endl;

    quickSort( pucBuff, sizeof(pucBuff)/4 );
    cout << "排序后\n" << endl;
    for( unsigned int i = 0; i < sizeof(pucBuff)/4; i++ )
    {
        cout<< pucBuff[i]<< " ";
    }
    cout<<endl;
    return 1;
}

 

排序算法之快速排序


联系
我们