冒泡排序及其优化
2018-12-08 本文已影响49人
徒步青云
冒泡排序原理:通过交换相邻元素,来将未排序中最大(小)元素依次“冒泡”到数组最后方。
最原始的冒泡排序:
template<typename T>
void bubbleSort(T arr[], int n) {
//n-1次冒泡(最后1次自然有序)
for (int i = 0; i < n - 1; i++) {
//每次冒泡,相邻两个元素进行比较,将当前数组中最大元素移至末尾
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
从代码中我们可以发现,最原始的冒泡排序算法对相同规模的输入,其排序次数是固定不变的。然而经过一次次“冒泡”操作后,未排数据将趋于稳定(即有序),这是因为每次“冒泡”都是相邻元素进行比较和交换完成的。考虑到这种情况,我们便有了下面这种优化方案:
template<typename T>
void bubbleSort1(T arr[], int n) {
bool isSwap = true;//本次循环是否发生过数值交换,若false,则表示所有元素都有序
for (int i = 0; isSwap && i < n - 1; i++) {
isSwap = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
isSwap = true;
}
}
}
}
第一种改进方案虽然有一定的优化效果,但至是考虑了尾端元素有序的情况,并没有考虑到元素局部有序这种情况,因此我们有了第二种改进方案:
template<typename T>
void bubbleSort2(T arr[], int n) {
int lastSwapPos = n - 1;//最后一次交换的位置,此时后面数列顺序已经正确
int tempPos;
do {
tempPos = lastSwapPos;
lastSwapPos = 0;
for (int j = 0; j < tempPos; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
lastSwapPos = j;
}
}
} while (lastSwapPos > 0);
}
鸡尾酒排序
template<typename T>
void cocktailSort(T arr[], int n) {
int left = 0;
int right = n - 1;
while (left < right) {
for (int i = left; i < right; i++) { //向右进行“冒泡”
if (arr[i] > arr[i + 1])
swap(arr[i], arr[i + 1]);
}
right--;
for (int j = right; j > left; j--) { //向左进行“冒泡”
if (arr[j] < arr[j - 1])
swap(arr[j], arr[j - 1]);
}
left++;
}
}
改进的鸡尾酒排序
template<typename T>
void cocktailSort1(T arr[], int n) {
int left = 0;
int right = n - 1;
int swapPos = left;
while (left < right) {
for (int i = left; i < right; i++) { //向右进行“冒泡”
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapPos = i;//此时记录向右冒泡最后一次交换位置
}
}
right = swapPos;//将最后一次交换位置作为右冒泡起点
for (int j = right; j > left; j--) { //向左进行“冒泡”
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
swapPos = j;//此时记录向左冒泡最后一次交换位置
}
}
left = swapPos;//将最后一次交换位置作为左冒泡起点
}
}
image.png