(排序算法总结)快速排序c++实现--将未排序部分的最后一个数作为主元
#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;
}
运行结果:
这只是快速排序的一种实现方法,其他请参考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
注意:快速排序算法的时间复杂度是O(nlogn),证明方法比较难,想要研究的话可以自行百度。
https://blog.csdn.net/zhyh1435589631/article/details/51374083
不稳定排序算法记忆口诀:快些选队(快速排序,希尔排序,选择排序,堆排序)
还没有评论,来说两句吧...