常见的排序算法

   排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序。   

    常见的排序算法：冒泡、快排、插入、希尔、选择、堆排、归并。

1、冒泡排序

原理：一个无序数组，按照升序排列。int i 代表循环的次数，int j 代表数组的下标，if(arr[j]>arr[j+1]),交换位置，依次类推。每循环一次，一个数字在它相应的位置。

源码：

void Bubble_sort(int arr[],int len)
{
	int i;
	for(i=0;i<len;i++)
	{
		int j;
		for(j=0;j<len-1-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}

时间复杂度o(n^2),空间复杂度o(1).

2、快排：

原理：从中间向两边的探索，在序列中选择一个准基数，用来做参考的数，选择左边的第一个数为例，将序列中所有大于准基数的数放在它的右边，小于的放在它的左边，最终确定准基数的位置。

定义两个变量left、right，可以将其看作指针，指定其对应的某元素，一个指向最左边，一个指向最右边，选择left作为准基数，从最左边的数和它比较，当准基数小于right指向的数时，right--，如果大于right指向的数，arr[left]=arr[right],当准基数大于左边的值时，left++，如果小于左边的值，arr[right]=arr[left],最后将准基数放在其正确的位置，然后重复上述步骤递归。

源码：

void Quick_sort(int arr[],int Front,int Back)
{
	int left=Front;
	int right=Back;
	if (left < right)
	{
		int tmp = arr[left];
		while(left<right)
		{
			while (left < right && tmp < arr[right])
			{
				right--;
			}
			arr[left] = arr[right];
			while (left < right && tmp > arr[left])
			{
				left++;
			}
			arr[right] = arr[left];
		}
		arr[left] = tmp;
		Quick_sort(arr,Front,left-1);
		Quick_sort(arr,left+1,Back);
	}
}

时间复杂度o(nlog2n),空间复杂度o(nlog2n)

3、插入排序：

原理：插入排序就是讲一个数字插入到它本该占据的位置。

源码：

void Insertsort(int arr[],int len)
{
	int i = 0;
	for (i = 0; i < len-1; i++)
	{
		int tmp = arr[i+1];
		int pos = i;
		while (pos>=0 && arr[pos] > tmp)
		{
			arr[pos+1] = arr[pos];
			pos--;
		}
		arr[pos+1] = tmp;
	}
}

时间复杂度o(n^2),空间复杂度o(1).

4、希尔排序

原理：希尔排序就是基于插入排序的一种改进，先将整个待排元素分成若干个子序列（有相隔某个增量元素组成），分别进行插入排序，然后缩减增量再进行排序，待这整个元素基本有序时（增量足够小），再对全体元素进行一次插入排序。

源码：

void ShellSort(int arr[], int len)
{
	int gap = len;
	while (gap)
	{
		gap = gap/2;
		for (int i = gap; i < len; i++)
		{
			int tmp = arr[i];
			int pos = i-gap;
			while (pos>=0 && arr[pos] > tmp)
			{
				arr[pos+gap] = arr[pos];
				pos-=gap;
			}
			arr[pos+gap] = tmp;
		}
	}
}

时间复杂度o(n^2),空间复杂度o(1).

5、选择排序

原理：在待排序列中将第一个元素记为最小的，第一个位置记为最小位置，在剩余所有元素中找到最小的与之交换。

源码：

void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		int min = arr[i];
		int index = i;
		for (int j = i+1; j < len; j++)
		{
			if(arr[j] < min)
			{
				min = arr[j];
				index = j;
			}
		}
		arr[index] = arr[i];
		arr[i] = min;
	}
}

时间复杂度o(n^2),空间复杂度o(1).

6、堆排

将初始化序列构成大堆，此堆为初始的无序区，将堆顶元素与最后一个元素交换位置，得到一个无序区和一个有序区，交换后的堆顶元素不变，因此将堆顶元素向下调整，保证最大堆的性质。

源码：

void HeapDown(int arr[],int i,int len)
{
	int parent=i;
	int child=2*i+1;
	while (child < len)
	{
		if(child+1<len && arr[child]<arr[child+1])
		{
			child=child+1;
		}
		if(arr[child]>arr[parent])
		{
			swap(arr[parent],arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void CreateHeap(int arr[],int len)
{
	int i=0;
	for(i=len/2-1;i>=0;i--)
	{
		HeapDown(arr,i,len);
	}
}

void HeapSort(int arr[],int len)
{
	CreateHeap(arr,len);
	for (int i = len-1; i >= 0; i--)
	{
		swap(arr[0],arr[i]);
		HeapDown(arr,0,i);
	}
}

时间复杂度o(nlog2n),空间复杂度o(1).

7、归并排序

源码：

void MergeArray(int arr[], int low, int mid, int high,int a[])
{
	int i = low;
	int j = mid+1;
	int k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])
		{
			a[k] = arr[i];
			i++;
			k++;
		}
		else
		{
			a[k] = arr[j];
			j++;
			k++;
		}
	}
	while (i<=mid)
	{
		a[k] = arr[i];
		i++;
		k++;
	}
	while (j <= high)
	{
		a[k] = arr[j];
		j++;
		k++;
	}
	for (i = 0; i < k; i++)
	{
		arr[low+i] = a[i];
	}
}

void MSort(int arr[],int first, int last, int a[])
{
	if(first < last)
	{
		int mid = (first+last)/2;
		MSort(arr,first,mid,a);
		MSort(arr,mid+1,last,a);
		MergeArray(arr,first,mid,last,a);
	}
}

void Mergesort(int arr[], int sz)
{
	int *a = new int[sz];
	MSort(arr,0,sz-1,a);
	delete []a;
}

时间复杂度o(nlog2n),空间复杂度o(n)。