八大排序算法及其优化-ag真人游戏

常见的排序算法

1. 直接插入排序

（1）算法基本思想

（2）特性总结：

1. 元素集合越接近有序，直接插入算法的时间效率越高
2. 时间复杂度：o(n^2)
3. 空间复杂度：o(1)，它是一种稳定的排序算法
4. 稳定性：稳定

（3）代码实现：

void insertsort(int* a, int n)
{ 
	for (int i = 0; i < n - 1; i)
	{ 
		int end = i;
		int tmp = a[end  1];
		while ()
		{ 
			if (tmp > a[end])
			{ 
				a[end  1] = a[end];
				end--;
				a[end  1] = tmp;
			}
			else
				break;
		}
	}
}

2. 希尔排序

（1）算法基本思想

（2）特性总结：

1. 希尔排序是对直接插入排序的优化
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： o(n^1.3—n2）
4. 稳定性：不稳定

（3）代码实现：

void shellsort(int* a, int n)
{ 
	int gap = n;
	while (gap > 1)
	{ 
		gap = gap / 3  1;
		for (int i = 0; i < n - gap; i)
		{ 
			if (a[i] > a[i  gap])
			{ 
				int tmp = a[i];
				a[i] = a[i  gap];
				a[i  gap] = tmp;
			}
		}
	}
}

3. 直接选择排序

（1）算法基本思想

（2）特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：o(n^2)
3. 空间复杂度：o(1)
4. 稳定性：不稳定

（3）代码实现

void selectsort(int* a, int n)
{ 
	int min = 0;
	int max = 0;
	
		for (int i = 0; i<n-1; i)
		{ 
			min = i;
			
				for (int j = i; j < n-1; j)
				{ 
					if (a[min] > a[j  1])
					{ 
						min = j  1;
					}
					
				}
				swap(&a[min], &a[i]);
		}		
}

4. 堆排序

需要注意的是排升序要建大堆，排降序建小堆。

（1）算法基本思想

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
（2）特性总结

1. 堆排序使用堆来选数，效率就高了很多
2. 时间复杂度：o(n*logn)
3. 空间复杂度：o(1)
4. 稳定性：不稳定

（3）代码实现

void ajustdown(int* a, int root, int n)
{ 
	int parent = root;
	int child = parent * 2  1;
	while (child < n)
	{ 
		if (a[child] < a[child  1] && child  1 < n)
			child;
		if (a[child] > a[parent])
		{ 
			int tmp = parent;
			parent = a[child];
			a[child] = tmp;
			parent = child;
			child = parent * 2  1;
		}
		else
			break;
	}
}
void heapsort(int* a, int root, int n)
{ 
	//建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{ 
		ajustdown(a, i, n);
	}
	int end = n;
	for (int i = end; i >= 0; i--)
	{ 
		swap(a[0], a[end]);
		ajustdown(a, 0, i);
	}
}

5. 冒泡排序

（1）基本思想

（2）特性总结

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：o(n^2)
3. 空间复杂度：o(1)
4. 稳定性：稳定

（3）代码实现

void bubblesort(int* a, int n)
{ 
	int flag = 0;//优化
	for (int i = 0; i < n - 1; i)
	{ 
		for (int j = 0; j < n - i; j)
		{ 
			if (a[j] > a[j  1])
			{ 
				swap(a[j], a[j1]);
				flag = 1;
			}
		}
		if (flag == 0)
			break;
}

6. 快排

（1）基本思想

（2）特性总结

1. 快排整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：o(n*logn)
3. 空间复杂度：o(logn)
4. 稳定性：不稳定

（3）代码实现
代码1：

#include
#include
int a[100], n;
void quicksort(int left, int right)
{ 
	int i;//指向第一个数
	int j;//指向最后一个数
	int tmp;//存基准数
	if (left > right)
		return;
	tmp = a[left];
	i = left;
	j = right;
	while (i != j)
	{ 
		while (i < j && a[j] >= tmp)
		{ 
			j--;
		}
		while (i < j && a[i] <= tmp)
		{ 
			i;
		}
		if (i < j)
		{ 
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	//最终将基准数归位
	a[left] = a[i];
	a[i] = tmp;
	quicksort(left, i - 1);//继续处理左边的，这里是一个递归的过程
	quicksort(i  1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{ 
	int i;
	//读入数据
	scanf("%d", &n);
	for (i = 1; i <= n; i)
		scanf("%d", &a[i]);
	quicksort(1, n); //快速排序调用
	//输出排序后的结果
	for (i = 1; i < n; i)
		printf("%d ", a[i]);
	system("pause");
	return 0;
}

代码2：

//这里还有一种简单的，通俗易懂的快速排序方法，代码如下：
#include 
void swap(int a[],int i,int j)
{ 
	int t;
	t=a[i];
	a[i]=a[j];
	a[j]=t;
}
void quicksort(int a[],int left,int right)
{ 
	int mid,i,j;
	if(left>=right)
		return;
	mid = a[left];
	i=left;
	j=left1;
	while(j<=right)
	{ 
		if(a[j]<=mid)
		{ 
			i;
			swap(a,i,j);
		}
		j;
	}
	swap(a,i,left);
	quicksort(a,left,i-1);
	quicksort(a,i1,right);
}
int main()
{ 
	int a[9]={ 8,2,6,12,1,9,5,5,10};
	int i;
	quicksort(a,0,8);/*排好序的结果*/
	for(i=0;i<9;i)
	printf("%d\n",a[i]);
	return 0;
}

观察上面代码可知，j一直在向后移，而i只有在发生交换操作后才后移。可见，小于等于i坐标的数值都是小于等于mid值的，大于i坐标的数值都是大于mid值的。

i是先加1再交换的。

简单吧，通俗易懂吧，哈哈，希望对大家有帮助！

7. 归并排序

（1）基本思想

（2）特性总结

1. 归并排序的缺点在与需要o(n)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排问题
2. 时间复杂度：o(n*logn)
3. 空间复杂度：o(n)
4. 稳定性：稳定

（3）代码实现

void _mergesort(int* a, int left, int right, int* tmp)
{ 
	if (left >= left)
		return;
	//将它分为两部分
	int mid = left  ((right - left) >> 1);
	//[left, mid]
	//[mid 1, right]
	_mergesort(a, left, mid, tmp);
	_mergesort(a, mid  1, right, tmp);
	int begin1 = left, end1 = mid;
	int begin2 = mid  1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{ 
		if (a[begin1] < a[begin2])
			tmp[index] = a[begin1];
		else
			tmp[index] = a[begin2];
	}
	while (begin1 <= end1)
		tmp[index] = a[begin1];
	while (begin2 <= end2)
		tmp[index] = a[begin2];
	memcpy(a  left, tmp  left, sizeof(int)*(right - left  1));
}