快速排序的实现

快速排序

今天学习了快速排序，概念还是比较简单，在快速排序中用到了分治的概念，将数组按照一个基准分为两部分，将比基准大的数全部放到基准的右边，将比基准小的数全部放到基准的左边。并且重复这个操作。

首先定义变量 i，j temp并且分别另i=0；j=MaxSize-1 ； temp=arr[0];

开始从后往前找，如果遇到一个数比temp小，就交换arr[j]和arr[i]，在这一趟j变为6，i不变，并且arr[i]和arr[j]的值交换。

接着从前往后找，找到第一个大于arr[j]的数，就将它和arr[j]交换，在i=1处我们发现10>5,这里我们将arr[1]和arr[6]交换

下一步，5和1交换

下一步,7和5交换

最后，5和3交换

然后当j=i时循环已经结束了，我们发现5这个基准左边的数都小于5,并且右边的数都大于5，接下来我们把基准右边的数和基准左边的数分别再用上面的方法来处理。这是一个递归调用的过程。 下面直接上代码把。

#include<stdio.h>
#include<iostream>
#define MaxSize 15
using namespace std;
void quicksort(int arr[],int i,int j);
int onecount(int arr[],int i,int j);

int main()
{
    int arr[] = {21,32,88,43,98,150,54,32,133,45,119,23,4,66,86};

    int i,j,temp;

    i = 0;
    j = MaxSize -1;
    quicksort(arr,i,j);




    for(int l = 0;l<MaxSize;l++)
        printf("%d \t",arr[l]);

    return 0;

}

void quicksort(int arr[],int s,int e)//对arr中的元素进行快排
{
    int i ;
    if(s<e)
    {
        i = onecount(arr,s,e);
        quicksort(arr,s,i-1);
        quicksort(arr,i+1,e);
    }
}


int onecount(int arr[],int i,int j)//一次处理
{
    int temp = arr[i],flag=0;
    while(j>i)
    {
        if(!flag)
        {
            if(arr[j]<temp)
            {
                swap(arr[j],arr[i]);
                flag = 1;
            }
            else
            {
                j--;
            }
        }
        else
        {
            if(arr[i]>temp)
            {
                swap(arr[i],arr[j]);
                flag = 0;
            }
            else
            {
                i++;
            }
        }
    }
    return i;
}

最后贴一张结果截图

最好的情况下，每次划分都将n个元素划分为两个长度差不多相同的子区间，快速排序的时间复杂度为O(nlog2n) 空间复杂度为O(log2n)。
最坏的情况下，每次划分选取的基准都是当前无序取中最小或者最大的元素，时间复杂度可达O(n^2),空间复杂度为O(n)。