快排为什么比冒泡快？该如何解决

快排为什么比冒泡快？

C/C++ code

#include <stdio.h>  #define  NUM   10  void main ( )  {    int a[NUM], i, j, t, flag;    printf ("input %d numbers: \n", NUM);    for (i = 0; i < NUM; i++)       //输入NUM个整数        scanf ("%d", &a[i]);    for (i = 1; i < NUM; i++)       //轮次，共NUM-1次    {       flag = 0;       for (j = 0; j < NUM - i; j++)  //实现一次冒泡操作           if (a[j] > a[j+1])                  //交换a[j]和a[j+1]           {   t = a[j];   a[j] = a[j+1];  a[j+1] = t;  flag = 1;  }       if (flag = = 0)  break;    }    printf ("the sorted numbers:\n");  //输出排好序的数据    for (i = 0; i < NUM; i++)        printf ("%d ", a[i]);  }

是不是去掉了中间的值交换工作？

C/C++ code

void sort(__int64 pnum[],int right,int left){    int l=left,r=right;     __int64   prive=pnum[r];    while(l<r)    {        while(l<r&&pnum[l]<=prive)        l++;        while(l<r&&pnum[r]>prive)        r--;        temp(&pnum[r],&pnum[l]);    }    if(left<r)    sort(pnum,r-1,left);    if(l<right)    sort(pnum,right,l+1);}

我也让快排进行了值交换，但是还是快排快，为什么？

[解决办法]
冒泡排序相当于嵌套的两重循环，设要排序的数字个数为n，那么复杂度为O(n^2),而快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。最坏情况下的复杂度和冒泡一样，最好的情况复杂度为O（nlogn)

查看更多 下一篇