冒泡排序

参考【排序】：冒泡排序以及三种优化

//假设排序arr[] = { 1, 3, 4, 2, 6, 7, 8, 0 };
void BubbleSort(int arr[],int len)
{
	int i = 0;
	int tmp = 0;
	for (i = 0; i < len - 1; i++)//确定排序趟数
	{
		int j = 0;
		for (j = 0; j < len - 1 - i; j++)//确定比较次数，每次从第一个开始比
		{
			if (arr[j]>arr[j + 1])
			{
				//交换
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

优化1——设置flag

假设我们现在排序arr[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。

void BubbleSort(int arr[], int len)
{
	int i = 0;
	int tmp = 0;
	for (i = 0; i < len - 1; i++)//确定排序趟数
	{
		int j = 0;
		int flag = 0;
		for (j = 0; j < len - 1 - i; j++)//确定比较次数
		{
			if (arr[j]>arr[j + 1])
			{
				//交换
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				flag = 1;//加入标记
			}
		}
		if (flag == 0)//如果没有交换过元素，则已经有序
		{
			return;
		}
	}
}

优化二——记录最后交换的位置

优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

void BubbleSort(int arr[], int len)
{
	int i;
	int tmp;
	int flag ;
	int pos;//用来记录最后一次交换的位置
	int k = len - 1;
	for (i = 0; i < len - 1; i++)//确定排序趟数
	{
		pos = 0;
		int j = 0;
		flag = 0;
		for (; j < k; j++)//确定比较次数,从第一个开始比
		{
			if (arr[j]>arr[j + 1])
			{
				//交换
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				flag = 1;//加入标记
				pos = j;//交换元素，记录最后一次交换的位置
			}
		}
		if (flag == 0)//如果没有交换过元素，则已经有序
		{
			return;
		}
		k = pos;//下一次比较到记录位置即可
	}
}

优化三——鸡尾酒排序

空

时间复杂度

最好情况$O(n)$,最坏和平均情况$O(n^2)$

空间复杂度

$O(1)$

稳定性

稳定

挖坑填数进行快速排序——固定基数

如果固定最左边的数作为基数，则要从右边开始循环。
如果固定最右边的数作为基数，则要从左边开始循环。

#include <iostream>
using namespace std;

int findidx(int* a, int low, int high)
{
	int temp = a[low];//拿左边的值当哨兵
	while (low < high) {
		while (low < high && a[high] >= temp) { high--; }//找到比哨兵小的放到low位置
		a[low] = a[high];
		while (low < high && a[low] <= temp) { low++; }//找到比哨兵大的放到high位置
		a[high] = a[low];		
	}
	a[high] = temp;//此时high==low,往这个位置放入哨兵值
	return high;
}

void qsort(int* array, int low, int high)
{
	if (low >= high)return;//当low>=high时，说明某个子序列就一个或没有元素了，该子序列就没必要排了
	int idx = findidx(array, low, high);
	qsort(array, low, idx - 1);
	qsort(array, idx + 1, high);
}

int main()
{
	int array[] = { 3,8,5,6,0,3,2,8,9,1,10 };
	int len = sizeof(array) / sizeof(array[0]);
	qsort(array, 0, len - 1);
	for (int i = 0; i < len; i++) {
		cout << array[i] << " ";
	}
	cout << endl;
	//0 1 2 3 3 5 6 8 8 9 10
}

时间复杂度

最差情况

一个序列完全有序（不管从小到大或是从大到小），每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)。时间复杂度为$O(n^2)$.

最优情况

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。递归算法公式为$T[n]=aT[n/b]+f(n)$,即把一个规模为n的问题分为a个规模为n/b的子问题。
这里复杂度为$T[n]=2T[n/2]+f(n)$,$f(n)$为平分这个数组所花的时间$O(n)$（即函数findidx）
$T[n]=2T[n/2]+n$——第一次递归
$T[n]=2(2T[n/4]+n/2)+n=2^{2}T(n/2^2)+2n$——第二次递归
$T[n]=2^{2}T(n/2^2)+2n=2^2(2T(n/2^3)+n/2^2)+2n=2^{3}T(n/2^3)+3n$——第三次递归
。。。
$T[n]==2^{M}T(n/2^M)+Mn$——第M次递归
此时平分的不能再平分，$n/2^M=1$,$M=lo{g}_{2}n$,即进行了$lo{g}_{2}n$次递归。
$T[n]==2^{M}T(n/2^M)+Mn=nT(1)+nlo{g}_{2}n=n+nlo{g}_{2}n=O(nlogn)$

平均情况

$O(nlogn)$

空间复杂度

首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；

最优情况

进行$lo{g}_{2}n$次递归,故为$O(logn)$

最差情况

退化为冒泡排序的情况，$O(n)$

平均情况

$O(logn)$

稳定性

优化方法

1.三数取中法

解决基本有序的序列（就是找到数组中最小下标，最大下标，中间下标的数字，进行比较，把中间大的数组放在最左边）

#include <iostream>
using namespace std;

void swap(int *array, int low, int high)
{
    int temp = array[low];
    array[low] = array[high];
    array[high] =temp;
}
int findidx(int *a, int low, int high)
{
    //最左边，最右边以及中间这3个数的中位数放在最左边
    int mid = (low + high) / 2;
    if(a[low]>a[high])//最左大于最右的时候，交换左右
	{
		swap(a,low,high);
	}
	if(a[mid]>a[high])//如果中间的>high ,交换
	{
		swap(a,mid,high);
	}
	if(a[mid]>a[low])//如果中间的>low，交换
	{
		swap(a,mid,high);
	}

    int temp = a[low]; //拿左边的值当哨兵
    while (low < high)
    {
        while (low < high && a[high] >= temp)
        {
            high--;
        } //找到比哨兵小的放到low位置
        a[low] = a[high];
        while (low < high && a[low] <= temp)
        {
            low++;
        } //找到比哨兵大的放到high位置
        a[high] = a[low];
    }
    a[high] = temp; //此时high==low,往这个位置放入哨兵值
    return high;
}

void qsort(int *array, int low, int high)
{
    if (low >= high)
        return; //当low>=high时，说明某个子序列就一个或没有元素了，该子序列就没必要排了
    int idx = findidx(array, low, high);
    qsort(array, low, idx - 1);
    qsort(array, idx + 1, high);
}

int main()
{
    int array[] = {3, 8, 5, 6, 0, 3, 2, 8, 9, 1, 10};
    int len = sizeof(array) / sizeof(array[0]);
    qsort(array, 0, len - 1);
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << " ";
    }
    cout<<"s"<<endl;
    cout << endl;
    //0 1 2 3 3 5 6 8 8 9 10
}

2.随机选取基准

#include <iostream>
#include <ctime>
using namespace std;

void swap(int *array, int low, int high)
{
    int temp = array[low];
    array[low] = array[high];
    array[high] = temp;
}
int findidx(int *a, int low, int high)
{
    srand((unsigned)time(nullptr)); //设置随系统时间变化的种子
    int pivotPos = rand() % (high - low + 1) + low ;//哨兵为from low to high中的一个 
    swap(a, low, pivotPos);//把哨兵放到最左边
    int temp = a[low]; //拿左边的值当哨兵
    while (low < high)
    {
        while (low < high && a[high] >= temp)
        {
            high--;
        } //找到比哨兵小的放到low位置
        a[low] = a[high];
        while (low < high && a[low] <= temp)
        {
            low++;
        } //找到比哨兵大的放到high位置
        a[high] = a[low];
    }
    a[high] = temp; //此时high==low,往这个位置放入哨兵值
    return high;
}

void qsort(int *array, int low, int high)
{
    if (low >= high)
        return; //当low>=high时，说明某个子序列就一个或没有元素了，该子序列就没必要排了
    int idx = findidx(array, low, high);
    qsort(array, low, idx - 1);
    qsort(array, idx + 1, high);
}

int main()
{
    int array[] = {3, 8, 5, 6, 0, 3, 2, 8, 9, 1, 10};
    int len = sizeof(array) / sizeof(array[0]);
    qsort(array, 0, len - 1);
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    //0 1 2 3 3 5 6 8 8 9 10
}