数据结构与算法【排序】

一、选择排序
选择排序的时间复杂度为O(N^2)的算法。
其思想是从当前位置到数组的尾部，选出最小的一个数，将其放在当前位置，然后当前位置加一，直到到数组的尾部。

#include
#include
using namespace std;
//选择排序函数定义
void Swap(vector&nums, int minindex, int i)
{
	int temp = nums[minindex];
	nums[minindex] = nums[i];
	nums[i] = temp;
}
void selectsort(vector&nums,int n)
{
	for (int i = 0; i < n; i++)
	{
		int minindex = i;         //定义最小下标，初始化为i
		for (int j = i; j < n; j++)    //开始在区间上寻找最小值
		{
			minindex = nums[minindex] > nums[j] ? j : minindex;   //利用三目运算符进行判断当前位置与minindex位置的数组元素大小
		}
		Swap(nums, minindex, i);     //调用Swap函数进行值得交换
	}
}
int main()
{
	vector nums = { 3, 1, 4, 5, 2, 6 };
	int n = nums.size();
	//调用选择排序的函数
	selectsort(nums, n);
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

二、冒泡排序
冒泡排序的时间复杂度也是O(N^2)的算法，冒泡排序的核心思想是从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。算法的核心在于每次通过两两比较交换位置，选出剩余无序序列里最大（小）的数据元素放到队尾。

#include
#include
using namespace std;
void Swap(vector&nums,int i,int j)
{
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];     //利用位运算中的异或进行交换,前提是i不等于j
}
void bubblesort(vector&nums, int n)
{
	for (int i = n - 1; i >= 0; --i)
	{
		for (int j = 0; j < i; j++)
		{
			if (nums[j]>nums[j + 1])
			{
				Swap(nums, j, j + 1);
			}
		}
	}
}
int main()
{
	vector nums = { 3, 1, 4, 5, 2, 6 };
	int n = nums.size();
	bubblesort(nums, n);
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

三、插入排序
插入排序是时间复杂度为O(N^2)的排序算法中较为重要的一种排序算法，其核心思想是把要插入的数与数组中各数逐个比较， 当找到第一个比插入数大的元素i时，该元素之前即为插入位置。然后从数组最后一个元素开始到该元素为止，逐个后移一个单元。最后把插入数赋予元素a[i]即可。如果被插入数比所有的元素值都小则插入最前位置。

#include
#include
using namespace std;
void Swap(vector&nums, int i, int j)
{
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}
void insertsort(vector&nums, int n)
{
	if (n < 2)
	{
		return;
	}
	for (int i = 1; i < n; i++)    //找0-i上
	{
		for (int j = i - 1; j >= 0 && nums[j]>nums[j + 1]; --j) //如果j+1小于j上的则交换
		{
			Swap(nums, j, j + 1);
		}
	}
}
int main()
{
	vector nums = { 3, 1, 4, 5, 2, 6 };
	int n = nums.size();
	insertsort(nums, n);
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

四、归并排序
归并排序是O(NlogN)的算法，归并排序是较为重要的一种排序算法，其利用了递归的思想。

#include
#include
using namespace std;
void mergesort(vector&nums, int L, int M, int R)
{
	vector assit(R - L + 1); //构造一个辅助数组
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	while (p1 <= M&&p2 <= R)
	{
		assit[i++] = nums[p1] > nums[p2] ? nums[p2++] : nums[p1++];
	}
	while (p1 <= M)
	{
		assit[i++] = nums[p1++];
	}
	while (p2 <= R)
	{
		assit[i++] = nums[p2++];
	}
	for (int j = 0; j < assit.size(); j++)
	{
		nums[L + j] = assit[j];
	}
}
void binary(vector&nums, int L, int R)
{
	if (L == R)
	{
		return;
	}
	int mid = L + ((R - L) >> 1);
	binary(nums, L, mid);
	binary(nums, mid + 1, R);
	merogesot(nums, L, mid, R);
}
int main()
{
	vectornums = { 3, 1, 4, 5, 2, 6 };
	int n = nums.size() - 1;
	binary(nums, 0, n);
	for (int i = 0; i <= n; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

归并排序的拓展之小和问题:

//在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一一个数组的小和。
//
//例子 : [1,3,4,2,5] 1左边比1小的数，没有 : 3左边比3小的数，1; 4左边比4小的数，1、 3; 2左边比2小的数，1; 5左比5小的数，1、3、4、2; 
//所以小和为1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16

#include
#include
using namespace std;
int mergesort(vector&nums, int L, int M, int R)
{
	vector assit(R - L + 1);
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	int res = 0;     //用来记录小和
	while (p1 <= M&&p2 <= R)
	{
		res += nums[p1]
		assit[i++] = nums[p1++];
	}
	while (p2 <= R)
	{
		assit[i++] = nums[p2++];
	}
	for (int j = 0; j < assit.size(); j++)
	{
		nums[L + j] = assit[j];
	}
	return res;
}
int binary(vector&nums, int L, int R)
{
	if (L == R)
	{
		return 0;
	}
	int mid = L + ((R - L) >> 1);
	return binary(nums, L, mid)+
		   binary(nums, mid + 1, R)+
		   mergesort(nums, L, mid, R);
}
int smallSum(vector&nums,int n)
{
	if (n < 1)
	{
		return 0;
	}
	return binary(nums, 0, n);
}
int main()
{
	vector nums = { 1, 3, 4, 2, 5 };
	int n = nums.size();
	cout << smallSum(nums, n - 1) << endl;
	system("pause");
	return 0;
}

五、快速排序
快速排序的时间复杂度为O(NlogN)的算法。其核心思想是将数组中的前N-1个元素与最后一个元素比较，小于的放到小于区，等于的放到等于区，大于的放到大于区，遍历完之后，将最后一个元素与大于区第一个元素进行交换，然后重复上述步骤。

#include
#include
#include
using namespace std;
void Swap(vector&nums,int i,int j)
{
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}
vector partition(vector&nums, int L, int R)
{
	int less = L - 1;
	int more = R;
	while (L < more)
	{
		if (nums[L] < nums[R])
		{
			Swap(nums, ++less, L++);
		}
		else if (nums[L]>nums[R])
		{
			Swap(nums, --more, L);
		}
		else
		{
			L++;
		}
	}
	Swap(nums, more, R);
	return { less + 1, more };
}
void quicksort(vector&nums, int L, int R)
{
	if (L < R)
	{
		vector p = partition(nums, L, R);
		quicksort(nums, L, p[0] - 1);
		quicksort(nums, p[1] + 1, R);
	}
}
void quicksort(vector&nums)
{
	if (nums.size() < 2)
	{
		return;
	}
	quicksort(nums, 0, nums.size() - 1);
}

int main()
{
	vectornums = {1,3,4,2,5};
	quicksort(nums);
	int n = nums.size();
	for (int i = 0; i < n; i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	cout << endl;
	system("pause");
	return 0;
}

六、堆排序

#include
#include
using namespace std;
void swap(vector&nums, int i, int j)  //完成两个数的交换操作
{
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}
void heapinsert(vector&nums,int index)   //生成最大堆
{
	while (nums[index] > nums[(index - 1) / 2])   //比较当前结点与双亲结点的大小
	{
		swap(nums, index, (index - 1) / 2);       //大的换交换
		index = (index - 1) / 2;                  //依此向上遍历所有双亲结点
	}
}
void heapify(vector&nums,int index,int heapsize)    //实现堆的调整
{
	int left = index * 2 + 1;   //左孩子的下标
	while (left < heapsize)     //该结点有左孩子
	{
		//将左孩子与右孩子中较大的值给下标larges
		int largest = left + 1 < heapsize&&nums[left + 1] > nums[left] ? left + 1 : left;
		//判断双亲结点与孩子之间的值，将较大结点的下标给largest
		largest = nums[largest]>nums[index] ? largest : index;
		if (largest == index)
		{
			break;
		}
		swap(nums, largest, index);
		index = largest;
		left = index * 2 + 1;
	}
}
void heapsort(vector&nums)
{        
	for (int i = 0; i < nums.size(); i++)
	{
		heapinsert(nums, i);
	}
	int heapsize = nums.size();
	swap(nums, 0, --heapsize);//将堆顶与数组中最后一个元素交换，这样最大值就到了最后
	while (heapsize>0)
	{
		heapify(nums, 0, heapsize);
		swap(nums, 0, --heapsize);
	}
}
int main()
{
	vector nums = { 1, 3, 4, 2, 5 };
	//以大根堆实现数组排序
	heapsort(nums);
	for (int i = 0; i < nums.size(); i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

七、基数排序

#include
#include
using namespace std;
int maxbits(vector&nums)
{
	int max = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[i]>max)
		{
			max = nums[i];
		}
	}
	int digit = 0;
	while (max != 0)
	{
		digit++;
		max = max / 10;
	}
	return digit;
}
int getDigit(int x, int k)
{
	int res = 0;
	while (k != 0)
	{
		res = x % 10;
		x = x / 10;
		k--;
	}
	return res;
}
void radixsort(vector&nums)
{
	int digit = maxbits(nums);
	int radix = 10;    //十进制
	int i = 0, j = 0;
	vector assit(nums.size());   //构造一个和nums数组大小一样的辅助数组
	for (int k = 1; k <= digit; k++)   //有多少位就要进出多少次
	{
		vector count(radix);
		for (i = 0; i < nums.size(); i++)
		{
			j = getDigit(nums[i], k);
			count[j]++;
		}
		for (i = 1; i 
			count[i] = count[i] + count[i - 1];    //求前缀数组
		}
		for (i = nums.size()-1; i >= 0; i--)
		{
			j = getDigit(nums[i], k);
			assit[count[j] - 1] = nums[i];
			count[j]--;
		}
		for (i = 0, j = 0; i < nums.size(); i++, j++)
		{
			nums[i] = assit[j];
		}
	}
}
int main()
{
	vector nums = { 45, 12, 36, 120, 111, 94 };
	radixsort(nums);
	for (int i = 0; i < nums.size(); i++)
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}