数据结构——排序算法——冒泡排序

冒泡排序1

void swap(vector<int> arr, int i, int j)
{int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}void bubbleSort1(vector<int> arr)
{for (int i = 0; i < arr.size() - 1; i++){for (int j = 0; j < arr.size() - 1 - i; j++){if (arr[j] > arr[j + 1]){// 如果左边的数大于右边的数，则交换，保证右边的数字最大swap(arr, j, j + 1);}}}
}

冒泡排序2

void bubbleSort2(vector<int> arr)
{//初始时 swapped 为 true ，省则则排序过程无法法启动bool swapped = true;for (int i = 0; i < arr.size() - 1; i++) {// 如果没有发生过交换，说明剩余部分已经有序，排序完成if (!swapped)break;// 设置 swapped 为 false，如果发生交换，则将其置为 trueswapped = false;for (int j = 0; j < arr.size() - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左边的数大于右边的数，则交换，保证右边的数字最大swap(arr, j, j + 1);// 表示发生了交换swapped = true;}}}
}

冒泡排序3

void bubbleSort3(vector<int> arr)
{bool swapped = true;// 最后一个没有经过排序的元素的下标int indexOfLastUnsortedElement = arr.size() - 1;// 上次发生交换的位置int swappedIndex = -1;while (swapped){swapped = false;for (int i = 0; i < indexOfLastUnsortedElement; i++){if (arr[i] > arr[i + 1]) {// 如果左边的数大于右边的数，则交换，保证右边的数字最大swap(arr, i, i + 1);// 表示发生了交换swapped = true;// 更新交换的位置swappedIndex = i;}}// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置indexOfLastUnsortedElement = swappedIndex;}
}