普通快速排序与随机化了的快速排序之间的区别

普通快速排序和随机化快速排序的主要区别在于它们的性能优化策略。

1. **普通快速排序（Non-Recursive Quick Sort）**：这是一种基本的分治排序算法，它选择数组中的一个元素作为“基准”（pivot），然后将数组分为两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于或等于基准。然后对这两部分递归地进行排序。最坏情况下，如果每次选择的基准都是当前部分的最大值或最小值，会导致分割不均衡，时间复杂度退化为O(n^2)。

2. **随机化快速排序（Randomized Quick Sort）**：为了避免最坏情况的发生，随机化快速排序引入了随机化的元素选择过程。在划分阶段，随机选择一个元素作为基准，这样可以使得分割更均匀，概率上降低了最坏情况的出现。由于随机性，平均来说，其性能接近于最优的O(n log n)。这种优化极大地提高了快速排序在实际应用中的效率。