基础的排序C++实现

好久没做算法，先练习一些基础的排序作为练手。

首先是插入排序（Insertion sort）的实现

<span style="white-space:pre">	</span>void InsertSort(int *a, int n)//n为数组长度
<span style="white-space:pre">	</span>{
<span style="white-space:pre">		</span>int j;
<span style="white-space:pre">	</span>
<span style="white-space:pre">		</span>for (j = 1; j < n; j++)
<span style="white-space:pre">		</span>{
<span style="white-space:pre">		</span>int key = a[j];
<span style="white-space:pre">		</span>int i = j - 1;
<span style="white-space:pre">		</span>while (i >= 0 && a[i] >= key)
<span style="white-space:pre">		</span>{
<span style="white-space:pre">			</span>a[i + 1] = a[i];
<span style="white-space:pre">			</span>i--;
<span style="white-space:pre">		</span>}
<span style="white-space:pre">		</span>a[i + 1] = key;
<span style="white-space:pre">		</span>}
<span style="white-space:pre">	</span>}
           

最快的快速排序，由划分数组和快排递归实现。

int Partition(int*a, int p, int q)//划分数组
{
	int x = a[p];
	int i = p;
	int j = 0;
	int temp = 0;
	for (j = p + 1; j < = q; j++)
	{
		if (a[j] <= x)
		{
			i++;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}

	temp = a[p];
	a[p] = a[i];
	a[i] = temp;

	return i; //return the pivot
}

void QuickSort(int*a, int p, int q)//递归排序
{
	if (p < q)
	{
		int r = Partition(a, p, q);
		QuickSort(a, p, r);//attention，是r不是r-1，要注意数组的上下界
		QuickSort(a, r + 1, q);	
	}
}
           

快排的循环实现方法，借助栈，每次把partition的左右结果，压入栈中，然后弹出，循环获得partition的结果。

void QuickSort2(int *a, int p, int q)//非递归
{
	stack<int> t;
	if (p < q)
	{
		int r = Partition(a, p, q);

		if (r - 1>p)
		{
			t.push(p);
			t.push(r - 1);
		}

		if (r + 1 < q)
		{
			t.push(r + 1);
			t.push(q);
		}

		while (!t.empty())
		{
			int right = t.top();
			t.pop();
			int left = t.top();
			t.pop();

			r = Partition(a, left, right);

			if (r - 1 > left)
			{
				t.push(left);
				t.push(r-1);
			}

			if (r + 1 < right)
			{
				t.push(r + 1);
				t.push(right);
			}

		}
	}
}
           

寻找一个无序数列中，排第i的数，也是用递归，结合上面的划分函数来进行，输出第四大的数，输出为6，也可以改为输出第n个数字。

#include<iostream>
#include<string>
using namespace std;
	
int Rand_Select(int *A, int p, int q)
{
	int x = A[p];//pivot
	int i = p;
	int j=0;
	int temp = 0;

	for (j = p + 1; j < q; j++)
	{
		if (A[j] < x)
		{
			i++;
			temp = A[j];
			A[j] = A[i];
			A[i] = temp;
		}

	}
	 temp = A[p];
	A[p] = A[i];
	A[i] = temp;

	cout << endl;
	return i;
}

	int getMid(int *A,int p,int q,int i)
	{
		if (p == q)
		{
			return A[p];
		}
		
		int r = Rand_Select(A, p, q);
		int k = r - p + 1;

		if (i == k)
		{
			return A[r];
		}
		else if (i < k)
		{
			return getMid(A, p, r - 1, i);
		}
		else
		{
			return getMid(A, r+1, q, i-k);
		}

	}




int main()
{

	int a[] = { 6, 10, 13, 5, 8, 3, 2, 11 };

	cout << getMid(a, 0, 7, 4) << endl;

	

	system("pause");//暂停程序

		return 0;
}
           

分治的归并排序，复杂度为O(nlogn)。

void merge(int *a, int left, int mid, int right)
{
	int *help = new int[right - left + 1];//
	int l = left;
	int r = mid + 1;
	int index = 0;
	while (l <= mid&&r <= right)
	{
		if (a[l] < a[r])
			help[index++] = a[l++];
		else
			help[index++] = a[r++];
	}

	while (l <= mid)
		help[index++] = a[l++];

	while (r<=right)
		help[index++] = a[r++];

	for (int i = 0; i < right - left + 1; i++)
		a[left + i] = help[i];

	delete[]help;//释放
}

void pocess(int *a, int left, int right)
{
	if (left == right)
		return;

	int mid = (left + right) / 2;

	pocess(a, left, mid);
	pocess(a, mid + 1, right);
	merge(a, left, mid, right);
}

void mergeSort(int *a,int n)
{
	if ((a == NULL) || n < 2)
		return;

	pocess(a, 0, n - 1);
}