表情包制作赚钱软件app哪个好用,邯郸seo排名,网站开发课程设计,番禺做网站哪家好快速排序算法最坏的时间复杂度时o(n*n)#xff0c;期望的运行时间为o(nlgn)。
逻辑分析#xff1a;
1 先从数组中选取一个数作为基数#xff0c;可随机选择#xff1b;
2 将数组中大于该基数的放在该基数右边#xff0c;小于该基数的放在该基数左边#xff1b;
3对左…快速排序算法最坏的时间复杂度时o(n*n)期望的运行时间为o(nlgn)。
逻辑分析
1 先从数组中选取一个数作为基数可随机选择
2 将数组中大于该基数的放在该基数右边小于该基数的放在该基数左边
3对左右两个数组重复第二步。
代码分析
数组a[]{2,1,4,5,3,8,7,9,0,6}该数组第一次分区时left0right10假设随机基数为a[4]3。
首先将a[0]和a[4]互换位置数组a[]{3,1,4,5,2,8,7,9,6,0}。
进行第一次分区 i0,j0时jleft数组没有改变没有改变。 i0j1时a[j]1a[left]3故交换a[i]和a[j]的位置i1故此时数组依然没有变化。 i1j2时a[j]4a[left]3此时数组仍然没有变化。 i1j3时a[j]5a[left]3此时数组仍然没有变化。 i1j4时a[j]2a[left]3故交换a[i]和a[j]的位置i2数组a[]{3,1,2,5,4,8,7,9,6,0}。 i2j5时a[j]8a[left]3此时数组仍然没有变化。 i2j6时a[j]7a[left]3此时数组仍然没有变化。 i2j7时a[j]9a[left]3此时数组仍然没有变化。 i2j8时a[j]6a[left]3此时数组仍然没有变化。 i2j9时a[j]0a[left]3故故交换a[i]和a[j]的位置i3数组a[]{3,1,2,0,4,8,7,9,6,5}。 i3跳出循环交换a[i]和a[left]的位置数组a[]{0,1,2,3,4,8,7,9,6,5。
#includeiostream
#includecstdlibusing namespace std;//交换a,b的值注意如果漏掉结果不正确
void swap(int a, int b)
{int temp a;a b;b temp;
}//分区 若a[j]基数则将a[j]的值和a[i]交换
int partition(int a[], int left, int right)
{int i left;for (int j left; j right; j){if (a[j] a[left]){swap(a[i], a[j]);}}swap(a[i], a[left]);return i;
}//快速排序 用随机法选取任意一个数数组内作为基数并将该数与a[left]互换
//递归方式对分区数组再进行划分
void quickSort(int a[], int left, int right)
{if (left right){int i left rand() % (right - left);swap(a[i], a[left]);int mid partition(a, left, right);quickSort(a, left, mid);quickSort(a, mid 1, right);}}int main()
{int a[] { 2,1,4,5,3,8,7,9,0,6 };quickSort(a, 0, 10);for (int i 0; i 10; i){cout a[i] ;}cout endl;system(pause);return 0;}
