冒泡排序（C++实现）

冒泡排序（C++实现）

        nums = [4, 1, 3, 1, 5, 2]

        N = 6;i从0~4；5层

void bubbleSort(vector &nums){
    int N = nums.size()
    for(int i =0; i nums[j+1]){
                //交换位置
                swap(nums[j] , nums[j+1]);
            }
        }
    }
}

关于优化

        通过增加一个标志位 flag ，若在某轮「内循环」中未执行任何交换 *** 作，则说明数组已经完成排序，直接返回结果即可。优化后的冒泡排序的最差和平均时间复杂度仍为 O(N^2)O(N^2) ；在输入数组 已排序 时，达到 最佳时间复杂度Ω(N) 。

void bubbleSort(vector &nums){
    int N = nums.size()
    for(int i =0; i nums[j+1]){
                //交换位置
                swap(nums[j] , nums[j+1]);
                只要发生交换就说明，有在实际排序
                //flag = ture;
            }
        }
        if(!flag)
               break;
                //没有实际排序了就跳出
    }
}

练习：

#define _CRT_SECURE_NO_WARNINGS
#include
using namespace std;
#include

void bubbleSort(vector &nums) {
	int N = nums.size();
	for (int i = 0; i < N - 1; i++) {          // 外循环
		bool flag = false;
		for (int j = 0; j < N - i - 1; j++) {  // 内循环
			if (nums[j] > nums[j + 1]) {
				// 交换 nums[j], nums[j + 1]
				swap(nums[j], nums[j + 1]);
				flag = true;
			}
		}
		if (!flag)
			break;
	}
}

void myprint(vector &nums) {
	for (vector::iterator it = nums.begin(); it != nums.end(); it++)
	{
		cout << *(it) << " ";
	}
	cout << endl;
}

void test()
{
	vector nums;
	for (int i = 0; i < 10; i++) {
		nums.push_back(i*rand() % 50 + 1);
	}

	cout << "初始数组" << endl;
	myprint(nums);

	bubbleSort(nums);

	cout << "排序数组" << endl;
	myprint(nums);
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}