黑马程序员技术交流社区

标题: 快速排序整理 [打印本页]
作者: Beacon    时间: 2014-10-23 14:20
标题: 快速排序整理
整理了一下快速排序。。。 大家一起学习！！！
  1. void sort(int arr[], int l, int r)
  2. {
  3.         int i = l;
  4.         int j = r;
  5.         int x = arr[i];
  6.         if(l < r)
  7.         {
  8.                 while(i < j)
  9.                 {
  10.                         while((i<j) && (arr[j]>x))
  11.                                 j--;
  12.                         arr[i] = arr[j];
  13.                         while((i<j) && (arr[i]<x))
  14.                                 i++;
  15.                         arr[j] = arr[i];
  16.                 }
  17.                 arr[i] = x;
  18.                 sort(arr, l, i-1);
  19.                 sort(arr, i+1, r);
  20.         }
  21. }

  23. int main()
  24. {
  25.         int i;
  26.         int arr[] = {18, 2, 15, 29, 12, 60};
  27.         sort(arr, 0, 5);
  28.         for(i = 0; i < 6; i++)
  29.                 cout << arr[i] << " ";
  30.         cout << endl;
  31.         return 0;
  32. }
复制代码


作者: 魔法少年十三    时间: 2014-10-23 22:55
这个输出语句明显是c++
作者: 弹琴骚年    时间: 2014-10-23 23:49
我记得好像还有更快的快排语句。。
作者: 崔石炫    时间: 2014-10-24 09:35
这不是递归排序么？
作者: 菜鸟_琦    时间: 2014-10-24 10:12
  1. 快排
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<time.h>
  5. #define MAX  100
  6. /*
  7. 快速排序算法的两个主要步骤，分割（Partition和QuickSort）
  8. */
  9. int Partition(int A[],int p,int q);
  10. int QuickSort(int A[],int p,int q);
  11. int test();
  12. int main()
  13. {
  14. test();
  15. return 0;
  16. }
  17. /*
  18. 一个很简单的测试函数
  19. */
  20. int test()
  21. {
  22. int a[MAX];
  23. int i;
  24. srand((int)time(0));
  25. for(i = 0;i<MAX;i++)
  26. {
  27.   
  28.   a[i] = rand();
  29. }
  30. for(i = 0;i<MAX;i++)
  31.   printf("%d\t",a[i]);
  32. printf("\n");
  33. QuickSort(a,0,MAX-1);
  34. for(i = 0;i<MAX;i++)
  35.   printf("%d\t",a[i]);
  36. printf("\n");

  38. }
  39. /*
  40. Partition步骤中哨兵选取的是最后一个元素作为哨兵
  41. */
  42. int Partition(int A[],int p,int q)
  43. {
  44. int i,j,x,t;
  45. x = A[q];
  46. i = p-1;
  47. for (j = p;j<=q;j++)
  48.   if(A[j] < x)
  49.   {
  50.    i++;
  51.    t = A[j];
  52.    A[j] = A[i];
  53.    A[i] = t;
  54.   }
  55. A[q] = A[i+1];
  56. A[i+1] = x;
  57. return i+1;
  58. }
  59. /*
  60. 递归调用的QuickSort程序
  61. */
  62. int QuickSort(int A[],int p,int r)
  63. {
  64. if(p<r)
  65. {
  66.   int q = Partition(A,p,r);
  67.   QuickSort(A,p,q-1);
  68.   QuickSort(A,q+1,r);
  69. }
  70. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2