数据结构与算法：C++实现快速排序

快速排序

思想&＃xff1a;先找到一个切分点&＃xff0c;然后使大于它的放后面&＃xff0c;小于它的放前面。切分将一个较大的随机数组分成两个随机子数组。

优点&＃xff1a;比较次数较少。

#includeusing namespace std;
void swap(int& a, int& b)
{int t &＃61; a;a &＃61; b;b &＃61; t;
}
int Parition(int* a, int from, int to)
{int h &＃61; from &＃43; 1;int l &＃61; to;int v &＃61; a[from];int t &＃61; 0;while (true){while (v >&＃61; a[h])  // 从左向右扫描找出比v大的那个位置{h&＃43;&＃43;;if (h &＃61;&＃61; to)break;}while (v <&＃61; a[l])  // 从右向左扫描找出比v小的那个位置{l--;if (l &＃61;&＃61; from)break;}if (h >&＃61; l)break;swap(a[h], a[l]); // 交换这两个位置}swap(a[l], a[from]); // 切分元素和左子数组的最右元素交换return l;}void QuickSort(int* a, int from, int to)
{if (from >&＃61; to)return;int key &＃61; Parition(a, from, to);QuickSort(a, from, key - 1);QuickSort(a, key &＃43; 1, to);
}int main()
{int a[] &＃61; { 12, 2, 3, 43, 5, 46, 74, 28, 30, 19, 11, 9 };int n &＃61; sizeof(a) / sizeof(int);QuickSort(a, 0, n - 1);for (int i &＃61; 0; i }

改进算法&＃xff1a;三向切分快速排序

将数组切分成三个部分&＃xff0c;分别是大于、小于和等于切分元素的数组元素&＃xff0c;适用于重复元素较多的数组。

void Quick3way(int* a, int from, int to)
{if (from >&＃61; to)return;int h &＃61; from; //小于切分元素的下标int l &＃61; to;int i &＃61; from &＃43; 1; // 等于切分元素的下标int v &＃61; a[from]; // 大于切分元素的下标while (i <&＃61; l){if (v > a[i]) //当a[i] v 时&＃xff0c; a[i]与最后的元素交换&＃xff0c;使最后元素的下标往前移一位{swap(a[l], a[i]);l--;}else //当a[i] &＃61; v 时&＃xff0c; 只有i往前移一位&＃xff0c;其余不变i&＃43;&＃43;;}Quick3way(a, from, h - 1);Quick3way(a, l &＃43; 1, to);
}