[数据结构与算法]数据结构--排序

数据结构–排序
冒泡排序

#include<iostream>
using namespace std;

//完善后的冒泡排序（从小到大）
//主要思路：通过比较相邻两个数字的大小，若左边的数字大于右边的数字就交换
void main()
{
	int size = 6;
	int x[6] = { 5,8,56,24,43,4 };
	int k;
	int flag;
	for (int m = 0; m < size - 1; m++)
	{
		flag = 1;
		for (int n = 0; n < size - 1; n++)
		{
			if (x[n] > x[n + 1])
			{
				k = x[n];
				x[n] = x[n + 1];
				x[n + 1] = k;
				flag = 0;
			}
		}
		//如果没有进行一次交换数据，就表明所有数字已经从小到大排序好
		if (flag == 1)
			break;
	}
	for (int i = 0; i < size; i++)
		cout << x[i]<<" ";
}

插入排序

#include<iostream>
using namespace std;

//插入排序
//主要思路：将数据分为有序区和无序区，不断从无序区取出数字在有序区找到合适的位置插入
//直到整个有序区为空
void main()
{
	int size = 6;
	int x[6] = { 5,8,56,24,43,4 };
	int k;
	int m;
	for (int i = 1; i < size; i++)
	{
		k = x[i];
		//找到插入的位置
		for (m = i; m >= 0; m--)
		{
			//如果比要插入的数大，就向后移
			if (x[m-1] > k)
			{
				x[m] = x[m-1];
			}
			else
				break;
		}
		x[m] = k;
	}
	for (int i = 0; i < size; i++)
		cout << x[i]<< " ";
}

选择排序

#include<iostream>
using namespace std;

//选择排序（从小到到排序）
//主要思路：将数据分为有序区和无序区两部分，从无序区选取最小的数据插入到有序区的末尾
void main()
{
	int size = 6;
	int x[6] = { 5,8,56,24,43,4 };
	int k;
	int min_x;
	for (int i = 0; i < size; i++)
	{
		min_x = i;
		for (int m = i; m < size; m++)
		{
			if (x[m] < x[min_x])
				min_x = m;
		}
		k = x[i];
		x[i] = x[min_x];
		x[min_x] = k;
	}
	for (int i = 0; i < size; i++)
		cout << x[i] << " ";
}

归并排序

#include<iostream>
using namespace std;

//归并排序
//主要思路：先将数据分成前后两部分，然后将前后两部分都排序好，最后将两部分按序进行组合（递归）
//递归公式：func(数组，q,r)=combin(func(数组的前一半，q,p),func(数组的后一半,p,r）)
//截止条件：p>=r

//将有序的两串数字进行有序组合
void combin(int* A,int a, int* B,int b)
{
	
	int m = 0;
	int n = 0;
	int i = 0;
	int* temp = new int[a + b];
	//比较A.B中的值，小的先进入数组temp，直到A,B的中的数据都进入数组temp
	while (m<a||n<b)
	{
		//如果A[m]的值小于B[n]的值且数组A没有遍历完   或    B已经遍历完，A还没遍历完
		if ((m != a&&A[m] <= B[n])||(n==b))
		{
			temp[i] = A[m];
			i++;
			m++;
		}
		else
		{
			temp[i] = B[n];
			i++;
			n++;
		}
	}
	for (i = 0; i < a + b; i++)
		A[i] = temp[i];
	delete temp;
}

void merger(int *data,int q,int r)
{
	if (q >= r)
		return;
	else
	{
		int p = (q + r) / 2;
		merger(data, q, p);
		merger(data, p+1, r);
		combin(data + q, p-q + 1, data + p+1, r-p);
	}
}
void main()
{
	//极端情况，只有一个数据
	int size_x = 1;
	int x[1] = {1};
	merger(x, 0, 0);
	for (int i = 0; i < size_x; i++)
		cout << x[i] << endl;

	cout << "\n";

	//普通情况
	int size_y = 6;
	int y[6] = { 5,8,56,24,43,4 };
	merger(x, 0, 0);
	for (int i = 0; i < size_y; i++)
		cout << y[i] << " ";
}

快速排序

#include<iostream>
using namespace std;

//快速排序（递归）
//主要思路：从要排序的数据中随机取出一个数（通常是第一个或最后一个），
//然后遍历所有其他数据，比这个数据小的放左边，比这个数据大的放右边，
//然后再继续对前后两个分区重复上述操作，直到无序区为空
//递归公式：func(数组，p,r)=partition(数组，p,r)+func(数组，p，q-1)+func(数组，q+1,r)
//终止条件：p>=r

//返回pivot值下标，并将数组数据按大小分散在这个值两侧
int partition(int* A, int p, int r)
{
	int pivort = A[r];
	//存储小于区和大于区的分界点
	int i = p;
	int item;
	//遍历所有除pivort外的所有数据
	for (int j = p; j <= r - 1; j++)
	{
		//如果数据比pivort小，就添加到小于区末尾，也就是和A[i]交换数据,然后i加一，表示分界点后移
		if (A[j] < pivort)
		{
			item = A[j];
			A[j] = A[i];
			A[i] = item;
			i++;
		}
	}
	//最后将A[i]和A[r]交换
	item = A[r];
	A[r] = A[i];
	A[i] = item;
	//最后返回pivort的位置
	return i;
}

void func(int* A, int p, int r)
{
	if (p >= r)
		return;
	else
	{
		int  q = partition(A, p, r);
		func(A, p, q - 1);
		func(A, q + 1, r);
	}
}

//快速排序函数，A为要排序的数组首地址，n为数组大小
void quick_sort(int *A,int n)
{
	func(A, 0, n - 1);
}




void main()
{
	//极端情况，只有一个数据
	int size_x = 1;
	int x[1] = { 1 };
	quick_sort(x, 1);
	for (int i = 0; i < size_x; i++)
		cout << x[i] << endl;

	cout << "\n";

	//普通情况
	int size_y = 6;
	int y[6] = { 5,8,56,24,43,4 };
	quick_sort(y, 6);
	for (int i = 0; i < size_y; i++)
		cout << y[i] << " ";
}

快速排序（改进）

// 快速排序优化
// 因为快速排序如果pivort点选择不好，可能时间复杂度会退化为O(n^2)
// 所以pivort点的选取需要进行优化
// 比较常用的分区算法有：1.三数取中法  2.随机法
// 1.三数取中法：将要排序的数据中的首、中、尾数据取出，进行比较，去中间值作为分区点
// 2.随机法：随机选取数据中的元素作为分区点
// 这里实现的是第一种优化方法

#include<iostream>
using namespace std;

// 分区点选择函数,返回中间值的下标
int get_pivort(int* A, int p, int r)
{
	int mid = (r + p) / 2;
	//当数据大小相同时，优先级从高到低为最后一个，第一个，中间
	if ((A[r] >= A[p] && A[r] <= A[mid]) || (A[r] >= A[mid] && A[r] <= A[p]))
		return r;
	else if ((A[p] >= A[r] && A[p] <= A[mid]) || (A[p] >= A[mid] && A[p] <= A[r]))
		return p;
	else
		return mid;
}

int partition(int* A, int p, int r)
{
	// 得到中间值的下标
	int a = get_pivort(A, p, r);
	// 如果分区点不是最后一个就将最后一个数据和分区点进行交换
	if (A[a] != A[r])
	{
		int item = A[r];
		A[r] = A[a];
		A[a] = item;
	}
	// 下面的操作和之前的相同
	int pivort = A[r];
	//存储小于区和大于区的分界点
	int i = p;
	int item;
	//遍历所有除pivort外的所有数据
	for (int j = p; j <= r - 1; j++)
	{
		//如果数据小于pivort，就添加到小于区末尾，也就是和A[i]交换数据,然后i加一，表示分界点后移
		if (A[j] < pivort)
		{
			item = A[j];
			A[j] = A[i];
			A[i] = item;
			i++;
		}
	}
	//最后将A[i]和A[r]交换
	item = A[r];
	A[r] = A[i];
	A[i] = item;
	//最后返回pivort的位置
	return i;

}

void func(int* A, int p, int r)
{
	if (p >= r)
		return;
	else
	{
		int  q = partition(A, p, r);
		func(A, p, q - 1);
		func(A, q + 1, r);
	}
}

//快速排序函数，A为要排序的数组首地址，n为数组大小
void quick_sort(int* A, int n)
{
	func(A, 0, n - 1);
}




void main()
{
	int t1 = time(0);

	//极端情况，只有一个数据
	int size_x = 1;
	int x[1] = { 1 };
	quick_sort(x, 1);
	for (int i = 0; i < size_x; i++)
		cout << x[i] << endl;

	cout << "\n";

	//普通情况
	int size_y = 6;
	int yyy[6] = { 5,8,56,24,43,4 };
	int y[6] = { 0 };
	// 想了个笨办法比较了一下改进之前和改进之后的效果
	for (int i = 0; i < 50000000; i++)
	{
		for (int m = 0; m < 6; m++)
			y[m] = yyy[m];
		quick_sort(y, 6);
	}

	cout << endl;
	int t2 = time(0);
	cout << t2 - t1;
}

总结：冒泡排序、插入排序、选择排序的时间复杂度都是O(n^2），且都是原地排序，适用于小规模数据的排序，不过比较来说还是插入排序性能更优，因为冒泡排序主要是交换操作，相比插入排序主要是比较和移动的操作，稍复杂一些。而选择排序虽然也都是比较的操作，但是它是不稳定的排序，排序前后相同数据的相对位置可能发生改变，而插入排序是稳定排序，不会改变相同数据的相对位置。归并排序和快速排序的平均时间复杂度都是O(nlogn)，比前三种的复杂度低，适用于大规模数据的排序，其中归并排序是稳定排序，但不是原地排序，排序过程中需要额外的内存空间，快速排序不是稳定排序，但是是原地排序，不需要额外的内存空间。这两者相比较还是快速排序更优，因为归并排序的空间复杂度是O(n)，其消耗的内存空间随着数据规模的增长而增长，当数据规模过于庞大时，内存消耗就会很大，所以虽然快速排序不是稳定排序，但它的应用跟广泛。