8大排序算法（超详细，算法步骤+代码）

1. 排序的分类

按照排序过程中所依据的原则的不同可以分类为:

►插入排序：直接插入排序 希尔排序

►交换排序：冒泡排序 快速排序

►选择排序：简单选择排序 堆排序

►归并排序

►基数排序

2. 排序算法比较

从平均情况看：堆排序、归并排序、快速排序胜过希尔排序。

从最好情况看：冒泡排序和直接插入排序更胜一筹。

从最差情况看：堆排序和归并排序强过快速排序。

虽然直接插入排序和冒泡排序速度比较慢，但是当初始序列整体或局部有序是，这两种算法的效率比较高。当初始序列整体或局部有序时，快速排序算法效率会下降。当排序序列较小且不要求稳定性是，直接排序效率较好；要求稳定性时，冒泡排序法效率较好。
8大排序算法：插入、冒泡、选择、希尔、归并（外部）、快速、堆、基数
内部排序：排序期间，元素全部放在内存中的排序
外部排序：排序期间，元素无法全部存放在内存中，必须在排序过程中根据要求不断地进行内外存之间移动排序
稳定性：指的是经过排序后，值相同的元素保持原来顺序的相对位置不变
1.冒泡排序：（全部按照升序排列）
思想：从第一个数开始，两两比较，如果第二个数比第一个数大，交换第一个数与第二个数的位置，相当于大泡泡往下沉了，一趟完了之后，最大的那个数就在最后一个位置了；然后继续比较，接下来是第二大的数字排在倒数第二个位置。。。

void BubbleSort(int arr[], int size)
{
	for (int i = 0; i < size-1; i++)
	{
		for (int j = 0; j < size-i-1; j++)
		{
			if (arr[j]>arr[j + 1])
			{
				int temp;
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j + 1] = temp;
			}
		}
	}
}

2.插入排序
思想：给一组数据，先对前一个元素进行排序（就是第一个数），然后对前两个数进行排序，再对前三个数进行排序。。。。一直到排完为止。

void InsertSort(int arr[], int size)
{
	int tmp,i,j;
	for (i = 1; i < size; i++)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (tmp < arr[j])//如果第二个数比第一个数大的话，就要交换
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
			
		}
		arr[j + 1] = tmp;
	}

}

3.希尔排序
希尔排序是在直接插入排序的基础上进行的改进：
1）首先计算整个数组大小，然后除以2，比如说原始数组中有8个元素，除以2之后那么跨度就是4，第1个元素和跨度为4的元素为一组，第2个元素与跨度为4的元素为一组，以此类推。这样下来，就会是两两一组，一共有4组，每组进行排序。
2）然后跨度为2，重复第1）步的过程
3）然后跨度为1，重复第1）步的过程

示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，增量的选择可以有很多种，我们在示例中所用的逐步折半的增量方法，是Donald Shell在发明希尔排序时提出的一种朴素方法，被称为希尔增量。

void ShellSort(int arr[], int size)
{
	int i, j,tmp,h;
	for (h = size / 2; h > 0; h /= 2)
	{
		for (i = h; i < size; i++)
		{
			tmp = arr[i];
			for (j = i - h; j>=0; j-=h)
			{
				if (tmp < arr[j])
				{
					arr[j + h] = arr[j];
				}
				else
				{
					break;
				}
			}
			arr[j + h] = tmp;
		}
	
	}
	
}

4.快速排序
算法思想：
分治法：比大小，再分区
1.从数组中选择一个数作为基准数，通常选择的是第一个数
2.分区：把比基准数小的数放在基准数的左边，把比基准数大的数放到基准数的右边。
3.再对左右区间重复第二步，直到区间中只有一个数。
实现思路：
挖坑填数
1.将基准数挖出形成第一个坑
2.由后向前找出比它小的数，找到后挖出此数填到前一个坑中
3.由前向后找比它大或等于的数，找到后挖出此数填到前一个坑中
4.重复2，3两步。

【5,3,9,1，6,7,2,4,0,8】
数组下标 0 1 2 3 4 5 6 7 8 9
数组元素 5 3 9 1 6 7 2 4 0 8
坑位 坑位1 坑位3 坑位5 坑位7 坑位6 坑位4 坑位2
0 4 2 5 7 6 9
0 3 4 1 2 5 7 6 9 8

通俗解释：就是先找一个基准数，通常是第一个数，然后把这个数对应的位置置为坑位1，然后先在右边找比基准数小的数，找到之后，把它对应的位置置为坑位2，然后把空位2的数放到坑位1中。然后从左边找比基准数大的数，找到的话记为坑位3，把坑位3的数，放到坑位2中。。。一直重复这个动作，最后只剩下一个坑位的时候，把基准数放到那个坑位中，这样就会使得基准数左边都是比它小的数，基准数的右边都是比它大的数。
这样的话，就是需要两个循环，分别是从左往右的循环和从右往左的循环。

void QuickSort(int arr[],int left, int right)
{
	int tmp, tmp2;
	int i, j;
	i = left;
	j = right;
	if (left >= right)
	{
		return;
	}
	int base = arr[left];
	while (i < j)
	{
		while (arr[j]>=base&&i<j)//从右向左找如果比基准数大的话，就往前移一个，如果比基准值小就挖坑
		{
			j--;
		}
		while (arr[i] <= base&&i<j)//从左往右找，如果比基准数小的话，就往后移一个，如果比基准数大的就挖坑
		{
			i++;
		}
		if (i < j)
		{
	    tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
		}
	
		
	}
	tmp2 = arr[i];
	arr[i] = arr[left];
	arr[left] = tmp2;
	QuickSort(arr,left, i - 1);
	QuickSort(arr, i + 1, right);
}

5.选择排序
遍历数组，每次把最大的一个元素放到最后一个位置，直到还剩下一个数字，此时数组就是有序的。

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

6.归并排序

归并排序的核心思想在于“分治”，所谓“分治”就是分而治之，把一个大的问题划分为许多小问题去解决，在处理数组排序时，如果数组中只有一个元素，那么我们就可以认为这个数组就是有序的，如果数组中有两个元素，那么最多只需比较一次就可得到排好序的数组，这就是分治算法的核心

归并排序就是，假设我们要排【3,2,5,1,4】这个数组，那么一般按照前原数组分成两部分的思想，这里可把原数组分成【3,2,5】和【1,4】然后可以继续分，直到分到单个元素为止
。
显然这个过程可以分为两个部分：
1.拆分过程：很明显适合使用递归写法，具体就是数组大小除2，一直这样，直到数组中元素个数为1
2.合并过程。
合并过程可分为3个部分，首先是把原数组分为左数组和右数组。第二部分就是根据大小进行拍戏，如果左数组中的元素大小小于右数组元素大小，就把左数组中元素放入数组中，反之将右数组中的元素放入数组中。第三部分：比较之后，可能左数组和右数组中有剩余的元素，将数组中剩余的元素放入数组中就可得到有序的数组。

void Divide(int arr[], int start, int end)
{
	while (start >= end)
	{
		return;
	}
	int mid = (start + end) / 2;
	Divide(arr, start, mid);
	Divide(arr, mid + 1, end);
}
void MergeSort(int arr[], int start, int mid, int end)//这块是合并过程
{
	//第一部分是将原数组中的元素分别存在左数组和右数组中
	int left[256] = { 0 };//左数组
	int right[256] = { 0 };//右数组
	int leftsize = mid - start + 1;
	int rightsize = end - mid;
	for (int i = 0; i < leftsize; i++)
	{
		left[i] = arr[i];
	}
	for (int j = 0; j < rightsize; j++)
	{
		right[j] = arr[j];
	}

	//第二部分主要是比较大小了
	int i=0, j=0, k=0;
	for (k = start; i < leftsize&&j < rightsize; ++k)
	{
		if (left[i] < right[i])
		{
			arr[i] = left[i];
			i++;
		}
		else
		{
			arr[j] = right[j];//i和j的范围之和就是整个数组的大小，因此不会出现覆盖的情况
			j++;
		}
	}
	//第三部分就是把左数组和右数组中剩下的元素放到arr中
	if (i < leftsize)//如果左数组中元素有剩余
	{
		for (; i < leftsize; i++)
		{
			arr[i] = left[i];
			++k;
		}
	}
	if (j < rightsize)//如果右数组中元素有剩余
	{
		for (; j < rightsize; j++)
		{
			arr[j] =right[j];
			++k;
		}
	}

}

7.堆排序
主要要依据堆结构，堆是一种具有特殊性质的完全二叉树（就是连着排的，中间没有空的），这个特殊性质就是，如果是大堆的话，那么根结点的值要大于两个孩子结点的值。如果是小堆的话，那么根节点的值要小于左右孩子结点的值。
【5,2,7,3,6,1,4】
思路：就是不断调整结点的位置，如果是升序的话，就调整成大堆的形式，调整成大堆的形式之后，此时堆顶元素就是最大的一个，取出堆顶的元素放到数组中的最后一个位置，此时堆顶就会空出一个位置，然后把二叉树的最后一个位置的元素放到堆顶，然后继续调整，使之成为一个大堆，然后取出堆顶元素，一直取，直到剩余一个元素，此时数组中就是一个升序序列。
写代码的时候，分成两个部分，首先要建堆，建堆的过程就是从最后一个非叶子结点开始向上调整，因为叶子结点最终都是要放到根节点的，所以就不用从叶子结点开始了，当然从叶子结点开始也是可以的，调整完了之后，将最后一个叶子结点与根节点进行交换，交换完了还得调整，因为可能此时已经不满足堆的性质了。
第二部分是具体的向上调整的过程：
这里有几点：
如果当前要访问的结点索引为i的话，那么
父节点索引：（i-1）/2
左孩子索引：2i+1;
右孩子索引：2i+2;
首先要判断如果左孩子索引小于数组大小，说明没调整完，如果左孩子数值大于最大索引位置的数值是，要把左孩子索引赋值给最大值索引。同理，右孩子也是一样。完了之后，如果发现此时最大值索引是不等于传入那个索引，也就是根节点索引的时候，说明需要交换位置了，就把最大值索引结点值与arr[index]值进行交换，交换完了再调整（只要交换了，就需要调整）

void UpAdjust(int arr[], int index, int size)
{
	int leftchild = 2 * index + 1;
	int rightchild = 2 * index + 2;
	int maxindex = index;
	if (leftchild < size&&arr[maxindex] < arr[leftchild])
	{
		maxindex = leftchild;
	}
	if (rightchild < size&&arr[maxindex] < arr[rightchild])
	{
		maxindex = rightchild;
	}
	if (maxindex != index)
	{
		swap(arr[maxindex], arr[index]);
		UpAdjust(arr, maxindex, size);
	}
}
void HeapSort(int arr[], int size)
{
	for (int i = size - 1; i >= 0; i--)
	{
		UpAdjust(arr, i, size);
	}
	for (int i = size-1; i >= 0; i--)
	{
		swap(arr[0], arr[i]);
		UpAdjust(arr, 0, i);
	}
}

8.基数排序
就是比如说一组数据【73,22,93,43,55,14,28,65,39,81】
先按照个位排序:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
然后把这些重新排序起来【81 22 73 93 43 14 55 65 28 39】
按照十位排序：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
然后把这些排序起来【14 22 28 39 43 55 65 73 81 93】

int maxbit(int data[], int n) 
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int tmp[n];
    int count[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
}