交换排序之——冒泡排序、快速排序

// test20.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<string.h>
#include<deque>
#include <forward_list>

using namespace std;

class Solution {
public:
	//冒泡排序
	void BubbleSort(vector<int> &vec)
	{
		for (int i = 0;i < vec.size();++i)
		{
			//第一个数字始终存储最小的数字
			for (int j = i + 1;j < vec.size();++j)
			{
				if (vec[i] > vec[j])
				{
					int num = vec[i];
					vec[i] = vec[j];
					vec[j] = num;

				}
			}
		}
		print(vec);
	}
	//改进后的冒泡排序
	//即当序列内不再发生交换时，不用再交换了，直接输出
	void BubbleSortImp(vector<int> vec)
	{
		int flag = 1;//flag==1时，要进行交换，否则不进行交换，结束循环
		for (int i = 0;i < vec.size() && flag == 1;++i)
		{
			flag = 0;
			for (int j = i + 1;j < vec.size();++j)
			{
				if (vec[i] > vec[j])
				{
					flag = 1;
					int temp = vec[i];
					vec[i] = vec[j];
					vec[j] = temp;
				}
			}
		}
		print(vec);
	}

	//快速排序
	//partion 将数组分为两种
	int partion(vector<int> &vec,int low,int high)
	{
	//	int num = vec[0];
		//先是从后面挑比自己小的放在前面

		while (low < high)
		{
			while (low < high && vec[low] <= vec[high] )
			{
				cout << "vec[high]:" << vec[high] << endl;
				--high;
				if (high == low) break;
			}
			if (low == high) //即low后面所有的数都大于等于num
			{
				break;
			}
			else 
			{ //如果不是，找到第一个小于num的数字，进行交换
				int temp1 = vec[high];
				vec[high] = vec[low];
				vec[low] = temp1;
				++low;
			}
			while (low<high&&vec[high]>vec[low]) //从前往后找第一个大于num的数
			{
				++low;
				if (high == low) break;
			}
			if (low == high)//即num前面的数都小于num
			{
				break;
			}
			else{
				int temp2 = vec[high];
				vec[high] =vec[low] ;
				vec[low] = temp2;
				--high; //一直是这个问题，导致程序调试不同，该打！！！！！！！！！！！！
			}
			
		}
			
// 	print(vec);
		return low;
		
	}
	//快速排序
	int flag = 0;
	void QuickSort(vector<int> &vec, int low, int high)
	{
		if(low<high)
		{
			int mid = partion(vec, low, high);
			QuickSort(vec, low, mid - 1);
			QuickSort(vec, mid + 1, high);
		}
	/*	if (low<high)
		{
			vector<int>::iterator mid = partion(vec, low, high);
			QuickSort(vec, vec.begin(), mid - 1);
			QuickSort(vec, mid + 1, high);
		}*/
		//print(vec);
	}

	void print(vector<int> &vec)//打印数据
	{
		for (auto it = vec.begin();it != vec.end();++it)
		{
			cout << *it << "  ";
		}
		cout << endl;
	}

};
int main()
{

	vector<int> vec = { 49,38,65,97,76,13,27,49};
//	vector<int> vec = { 1,9,7,6 };
	Solution so;
	//原来的序列
	cout << "原来的序列:   ";
	so.print(vec);
	//cout << "冒泡排序后的序列:   ";
	//so.BubbleSort(vec);
	/*cout << "改进后的冒泡排序后的序列:   ";
	so.BubbleSortImp(vec);*/

	cout << "第一遍后的快速排序:   ";
	//so.partion(vec,0,vec.size()-1);
	so.QuickSort(vec,0,vec.size()-1);
	so.print(vec);
	return 0;
}