快速排序算法的一些细节_快速排序移动次数

一 . 关于快速排序

快速排序是冒泡排序的改进算法。它也是通过不断比较和移动交换来实现排序的，只不过它的实现增大了记录的比较和移动的距离，将关键字较大的元素从前面直接放到后面，关键字较小的元素直接从后面放到前面，从而减小了比较次数和交换次数。

二 . 算法的具体实现

通过不断的函数循环调用以实现数据的正确排序，具体代码如下：

#include <iostream>
using namespace std;
void print(int *p,int len) 
{
    for (int i = 0; i <= len; i++)
    {
        cout << p[i];
    }
    cout << endl;
}
void Quick_Sort( int * arr, int begin,int end )
{
    cout << "当前数据:";
    print(arr,7);
    if (begin > end)
    return;   //函数循环的结束条件
    int tmp = arr[begin];
    int i = begin;
    int j = end;
      while (i!= j) 
      { while (arr[j] >= tmp && i< j)
              j--;
          while (arr[i]<=tmp&&i<j) 
              i++;      
              if (j > i)
              {
                  int t = arr[i];
                  arr[i] = arr[j];
                  arr[j] = t;
              }
      }
     /*int w = arr[i];
      arr[i] = arr[begin];
      arr[begin] = w;*/
      arr[begin] = arr[i];
      arr[i] = tmp;//1次循环结束
      Quick_Sort( arr,  begin, i-1);//前段
      Quick_Sort( arr,  i+1, end);//后段
}
int main()
{
    int a[8] = {5,9,3,2,6,3,8,1};
    cout << "初始数据:";
    print(a,7);
    Quick_Sort(a, 0, 7);
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

其中有2点细节个人认为可以自己实践体会

1. 关于i和j哪个先开始移动的点，在此程序中只能从j开始。我们假设从i先开始，那么a[i]每次完成一轮对调后所在的位置将会是比基准值大的第一个位置，试数据偏离。在初始化i和调用时进行加1或者减1的操作。因此显然从j开始检测数值来消除基准值在第一位而对i的影响更为简便。
2. 关于循环中对基准值进行对调时的数值对调，有2种方法。
   第一种为常规的对调，故可以设置一个换值函数同时替换此处以及上面的数值对换。（此处注意对调的虽为基准值，但基准值本身的位置是arr[begin]，故实际对调的为arr[i] 和arr[begin]）
   第二种为利用基准数和arr[begin]相同，在不改变基准值的情况下是数值对调。

/*int w = arr[i];
      arr[i] = arr[begin];
      arr[begin] = w;*///第一种


      arr[begin] = arr[i];
      arr[i] = tmp;//第二种

1
2
3
4
5
6
7
8

具体运行数据