(排序算法总结)快速排序c++实现--将未排序部分的最后一个数作为主元

今天药忘吃喽~ 2022-06-01 01:26 32阅读 0赞

#include <iostream>
    
    using namespace std;
    int Partition(int arr[],int low,int high)
    { int x=arr[high];
      int mid=low-1;
      for(int i=low;i<high;i++)
      { if(arr[i]<x)
         {mid++;
          swap(arr[i],arr[mid]);
         }
      }
      swap(arr[high],arr[mid+1]);
      return mid+1;
    }
    
    void QuickSort(int arr[],int low,int high)
    { int k;
      if(low<high)
        { k = Partition(arr,low,high);//k表示左右区间排序完成之后主元的位置
          QuickSort(arr,low,k-1);
          QuickSort(arr,k+1,high);
        }
     return;
    }

int main()
    {   int array1[]={2,4,3,6,15,7,9,13,7};
       int sizearray = sizeof(array1) /sizeof(int);
        //快速排序
        int low=0;
        int high=sizearray-1;
        QuickSort(array1,low,high);
        for(int i=0;i<sizearray;i++)
           cout << array1[i] << endl;
        return 0;
    }

运行结果:

![SouthEast][]

这只是快速排序的一种实现方法，其他请参考[https://www.cnblogs.com/mfryf/archive/2012/08/06/2625300.html][https_www.cnblogs.com_mfryf_archive_2012_08_06_2625300.html]

注意：其中swap函数是c++标准库自带的函数，定义方式为swap(T&a,T&b)，表示引用传递，因此调用的时候不应该写成swap(&x,&y)。详细请参考[http://blog.csdn.net/gdut2015go/article/details/49094741][http_blog.csdn.net_gdut2015go_article_details_49094741]

注意：快速排序算法的时间复杂度是O(nlogn)，证明方法比较难，想要研究的话可以自行百度。

![SouthEast 1][]

![70][]

[https://blog.csdn.net/zhyh1435589631/article/details/51374083][https_blog.csdn.net_zhyh1435589631_article_details_51374083]

不稳定排序算法记忆口诀：快些选队（快速排序，希尔排序，选择排序，堆排序）

[SouthEast]: /images/20220601/a0160887472c410d9892a357d28b1d96.png
[https_www.cnblogs.com_mfryf_archive_2012_08_06_2625300.html]: https://www.cnblogs.com/mfryf/archive/2012/08/06/2625300.html
[http_blog.csdn.net_gdut2015go_article_details_49094741]: http://blog.csdn.net/gdut2015go/article/details/49094741
[SouthEast 1]: /images/20220601/5b83dbd55e2a42319c1ab3ee285121f7.png
[70]: /images/20220601/dcb4c9fc3483417aadb9449d3b12eeae.png
[https_blog.csdn.net_zhyh1435589631_article_details_51374083]: https://blog.csdn.net/zhyh1435589631/article/details/51374083