【算法】经典排序

1.平均表现最优的快排

• 时间复杂度O(NlogN)

• 空间复杂度O(1)

• 缺点：不是稳定的，会交换值相同的元素的位置

void swap(int *a, int *b)
{
	if (a==NULL || b==NULL || a==b || *a=*b)
		return;

	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int size, int left, int right)
{
	if (a==NULL || size<=0 || left>=right)
		return -1;

	int i = left;
	int j = right+1;
	int pivot = a[left];
	while (ipivot) {
			if (j==left)
				break;
		}

		if (i>=j)
			break;

		swap(&a[i], &a[j]);
	}

	swap(&a[left], &a[j]);

	return j;
}

void QSort(int a[], int size, int left, int right)
{
	if (size<=0 || left>=right)
		return;

	int pindex = partition(a, size, left, right);
	QSort(a, size, left, pindex-1);
	QSort(a, size, pindex+1, right);
}

void qsort(std::vector &nums)
{
	int size = nums.size();
	if (size<=1) return ;

	QSort(&nums[0], size, 0, size-1);
}

2.稳定排序首选归并排序

• 时间复杂度O(NlogN)

• 空间复杂度O(N)

• 缺点：空间复杂度相对较高，需要额外数组大小的空间

void merge(int a[], int size, int tmp[], int left, int mid, int right)
{
	if (a==NULL || size<=0 || left>=right)
		return	;

	int i = left;
	int j = mid+1;
	int k = left;
	while (i<=mid && j<=right)
	{
		if (a[i]=right) return;

	int mid = left + (right-left)/2;
	MSort(a, size, tmp, left, mid);
	MSort(a, size, tmp, mid+1, right);
	merge(a, size, tmp, left, mid, right);
}

void mergeSort(std::vector &nums)
{
	int size = nums.size();
	if (size<=1) return	;

	std::vector tmp(size, 0);
	MSort(&nums[0], size, tmp, 0, size-1);
}