C++三大经典排序之选择排序、快速排序、冒泡排序

  最近这段时间，秋招正在火热的进行中，一想到秋招就不得不谈到面试，而且一想到面试，就不得不被问一些基础知识了，而这其中最经典的当属排序问题了。

面试官：你知道关于排序的一些问题吗？

应聘者：我知道啊，比较经典的有选择排序、快速排序、冒泡排序。

面试官：那你能具体谈谈这些排序吗？

应聘者：选择排序就是每次比较一下所有的数，然后排出一个沉到端点，接着再对未排序的数继续排，直到所有数都排完；快速排序就是每次选取一个数，然后比较，比它大的数放右边，比它小的数放左边，再通过递归的方式对两边的数继续排，直到所有数都排序完毕；冒泡排序就是两两比较，然后每一轮沉一个数到端点，这样子每一轮新的排序都会少比较一次。直到排序完毕。

面试官：嗯，那这些的算法的稳定性如何？

应聘者：衡量一个算法稳定与否，是看一个待排序序列中有相同元素时，它们的相对位置前后会不会发生改变。这其中，只有冒泡排序时稳定排序。

面试官：嗯，那你能用c++简单的写一下这三个排序的代码吗？

应聘者：...........................................................................................

会说还要会写，会写还要写对，写对还要能运行。话不多说，直接走起。

#include 
using namespace std;
//定义一个全局的数组，里面有7个数
int a[7] = { 9,7,16,32,5,13,26 };
//定义一个两数比较大小的函数，通过指针传递，这里选择排序和冒泡排序会用到
void swap(int* a, int* b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
//选择排序
void selectsort(int a[], int n)//参数1：要排序的数组  参数2：要排序的数组的个数
{
	//定义一个int型变量，用来接收最小值
	int min = 0;
	for (int i = 0; i < n; i++)
	{
		min = i;//假设第一个数是最小值
		for (int j = i+1; j < n; j++)//遍历第二个到第七个数
		{
			if (a[j] < a[min])
			{
				min = j;//如果后面的数比前面的数小，则将后面比较小的值移到min,这样min一直都会是最小值
			}
		}
		if (min != i)
		{
			//比较完一轮后，最小值就是a[min],如果它和min和i不相等，则交换值的大小
			//使得每一轮比较值都会沉到一端
			swap(a[i], a[min]);
		}
	}
}
//冒泡排序法
void Bubsort(int a[], int n)//参数1：要排序的数组  参数2：要排序的数组的个数
{
	//一个数组有n个数，则要排n轮
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			//两两相比较，所以每轮一共比较n-1，但是每一轮过过，都会有一个极值沉底，所以要n-1-i
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
			}
		}
	}
}

//快速排序
void quicksort(int arry[],int L,int R)//L为开始的点的下标，R为结束的点的下标
{
	if (L >= R)
	{
		return;
	}
	int left = L, right = R;
	//这个pivot存放中间点
	int pivot = arry[left];
	//假设选取最左边的点为中间点，则第一次要从最右边找，找到比中间点小的数，放到它左边，第二次从
	//右边找，找到比他大的值放右边，依次类推
	while (left=pivot)
		{
			right--;
		}
		arry[left] = arry[right];	
		while (left < right && arry[left]<=pivot)
		{
			left++;
		}
		arry[right] = arry[left];
		if (left == right)
		{
			arry[left] = pivot;
		}
	}
	//通过递归再比较
	quicksort(arry, L, left - 1);
	quicksort(arry, left + 1, R);
}


int main()
{
	quicksort(a, 0, 6);
	//selectsort(a, 7);
	//Bubsort(a,7);

	for (int i = 0; i < 7; i++)
	{
		cout << a[i] << " ";
	}
	
	return 0;
}

运行结果如图

结束。