## 快速排序

``````#include <iostream>
#define SPACE 0x100

using namespace std;

struct Data
{
int key;
};

struct SqList
{
Data r[SPACE];
int length;
};

int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
int pivotkey = L.r[low].key; // 用子表的第一个记录作枢轴记录
Data temp;
// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
temp = L.r[high];
L.r[high] = L.r[low];
L.r[low] = temp;

while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
temp = L.r[high];
L.r[high] = L.r[low];
L.r[low] = temp;
}
return low; //返回枢轴所在位置
}

void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}

int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);
int result = Partition(list, 1, list.length);
print(list, 1, list.length);
return 0;
}``````

``````[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 34, 7, 4, 37, 29, 74, 85, 95, 86, 99, ]``````

``````#include <iostream>
#define SPACE 0x100

using namespace std;

struct Data
{
int key;
};

struct SqList
{
Data r[SPACE];
int length;
};

int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low];			 // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字

// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];

while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}

L.r[low] = L.r[0]; // 枢轴记录到位
return low;		   //返回枢轴所在位置
}

void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}

int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);
int result = Partition(list, 1, list.length);
print(list, 1, list.length);
return 0;
}
``````

``````[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 34, 7, 4, 37, 29, 74, 85, 95, 86, 99, ]``````

``````#include <iostream>
#define SPACE 0x100

using namespace std;

struct Data
{
int key;
};

struct SqList
{
Data r[SPACE];
int length;
};

int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low];			 // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字

// 从表的两端交替地向中间扫描
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];

while (low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}

L.r[low] = L.r[0]; // 枢轴记录到位
return low;		   //返回枢轴所在位置
}

void QSort(SqList &L, int low, int high)
{
// 对顺序表 L 中的子序列 L.r[low .. high]作快速排序
if (low < high) // 长度大于 1
{
int pivotloc = Partition(L, low, high); // 将 L.r[low .. high]一分为二
QSort(L, low, pivotloc - 1);			// 对低子表递归排序, pivotloc 是枢输位置
QSort(L, pivotloc + 1, high);			// 对商子表递归排序
}
}

void QuickSort(SqList &L)
{
// 对顺序表 L 作快速排序。
QSort(L, 1, L.length);
}

void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}

int main()
{
SqList list = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list.length = 10;
print(list, 1, list.length);

QuickSort(list);

print(list, 1, list.length);
}``````

``````[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 4, 7, 29, 34, 37, 74, 85, 86, 95, 99, ]``````

### 快速排序的关键字比较次数与元素初始排列次序是有关系的

``````#include <iostream>
#define SPACE 0x100

using namespace std;

int amount; //用于统计判断次数

struct Data
{
int key;
};

struct SqList
{
Data r[SPACE];
int length;
};

int Partition(SqList &L, int low, int high)
{
// 交换顺序表 L 中子表 L.r[low .. high].key的记录,使枢轴记录到位,并返回其所在位置,此时
// 在它之前(后)的记录均不大(小)于它。
L.r[0] = L.r[low];			 // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字

// 从表的两端交替地向中间扫描
while (low < high)
{
while (++amount && low < high && L.r[high].key >= pivotkey)
{
--high;
}
// 将比枢轴记录小的记录交换到低端
L.r[low] = L.r[high];

if (low == high)
{
break;
}
#endif

while (++amount && low < high && L.r[low].key <= pivotkey)
{
++low;
}
// 将比枢轴记录大的记录交换到高端
L.r[high] = L.r[low];
}

L.r[low] = L.r[0]; // 枢轴记录到位
return low;		   //返回枢轴所在位置
}

void QSort(SqList &L, int low, int high)
{
// 对顺序表 L 中的子序列 L.r[low .. high]作快速排序
if (low < high) // 长度大于 1
{
int pivotloc = Partition(L, low, high); // 将 L.r[low .. high]一分为二
QSort(L, low, pivotloc - 1);			// 对低子表递归排序, pivotloc 是枢输位置
QSort(L, pivotloc + 1, high);			// 对商子表递归排序
}
}

void QuickSort(SqList &L)
{
// 对顺序表 L 作快速排序。
QSort(L, 1, L.length);
}

void print(SqList &L, int low, int high)
{
cout << "[ ";
for (int i = low; i <= high; i++)
{
cout << L.r[i].key << ", ";
}
cout << "]" << endl;
}

int main()
{
//list1 的结果
amount = 0;
SqList list1 = {NULL, 74, 99, 86, 95, 85, 29, 37, 4, 7, 34};
list1.length = 10;
print(list1, 1, list1.length);

QuickSort(list1);

print(list1, 1, list1.length);
cout << amount << endl
<< endl;

//list2 的结果
amount = 0;
SqList list2 = {NULL, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
list2.length = 10;
print(list2, 1, list2.length);

QuickSort(list2);

print(list2, 1, list2.length);
cout << amount << endl;
}
``````

``````[ 74, 99, 86, 95, 85, 29, 37, 4, 7, 34, ]
[ 4, 7, 29, 34, 37, 74, 85, 86, 95, 99, ]
40

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ]
54``````