常用的简单排序之插入排序，冒泡排序，选择排序，希尔排序-创新互联

1、插入排序

  插入排序的工作原理是建立有序序列，对于未排序数据，在已排序的数据从后先前扫描，找到对应的位置后插入。

  ①从第一个元素开始，该元素被默认为有序序列。

  ②从下一个未排序数据开始，在已经排序的序列中从后往前扫描

  ③如果该元素小于已排序的元素，继续往前扫描

  ④重复③，直到找到该元素大于或等于已排序的元素的位置

  ⑤插入该元素

  ⑥重复②

代码：

void InsertSort(int *a,int size)
{
	assert(a);
	for (int i = 1; i < size; i++)
	{
		int index = i;
		int end = index - 1;         //已排序序列最后一个元素下标
		int temp = a[index];         //保存未排序数据的值
		while (end >= 0 && temp < a[end])
		{
			a[end + 1] = a[end]; //当为排序数据小于已排序序列数据时，把已排序数据向后移一位
			end--;  //继续往前扫描
		}
		a[end + 1] = temp; //找到未排序数据大于或等于已排序序列，或者整个已排序序列没有一个数小于未排序数据时
	}
}

 插入排序对几乎已经排好序的数据进行操作时，效率很高。但插入排序一般来说是低效的，每次只能挪动数据一位。

2、选择排序

 选择排序的思想是每一趟从待排序的数据元素中选出最小的一个元素，顺序放在已排好序的数列的最前，直到全部待排序的数据元素排完。

void SelectSort(int *a,int size)

{

 assert(a);

 for(int i=0;i

 {

  int min=i;

  for(int j=i+1;j

  {

   if(a[min]>a[j])

    min=j;

  }

  swap(a[i],a[min]);

 }

}

还可以优化，我们可以在选出最小的元素放在序列头的同时，选出大的元素放在序列尾

void SelectSort(int *a, int size)
{
	assert(a);
	for (int left = 0, right = size - 1;left<=right;left++,right--)
	{
		int max = right, min = left;
		for (int i = left; i <= right; i++)
		{
			if (a[min] > a[i])
				swap(a[min],a[i]);
			if (a[max] < a[i])
				swap(a[max],a[i]);
		}
		swap(a[min], a[left]);
		swap(a[max], a[right]);
	}

3、冒泡排序

 从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，一个大的数沉底成为数组中的最后一个元素，一些较小的数如同气泡一样上浮一个位置。

void BubSort(int* a,int size)
{
	for (int i = 0; i < size; i++)
	{
		int symbol = false;
		for (int j = 1; j < size - i ; j++)
		{
			if (a[j] < a[j - 1])
				swap(a[j], a[j - 1]);
				symbol = true; 
		}
		if (symbol == false) //当symbol为false时，就说明后面的已经有序
			break;
	}
}

4、希尔排序

 希尔排序其实是更优化的插入排序。

 其思想为：

    把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

void ShellSort(int *a, int size)
{
	assert(a);
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = gap; i < size; i++)//比如当gap=4时，并不是让它分别进行4组插入排序，而是采用一种比较巧的方法，让i从gap开始每次加1，这样就能把4组插入排序，一次走完
		{
			int index = i;
			int temp = a[index];
			int end = index - gap;
			while (end >= 0 && temp
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
                

                分享名称：常用的简单排序之插入排序，冒泡排序，选择排序，希尔排序-创新互联                

                转载来于：http://dzwzjz.com/article/ceeeoj.html