数据结构·排序

排序的基本概念

排序的定义

• 排序
• 稳定性
• 分类
  • 按是否全部读入内存
    • 内部排序
    • 外部排序
  • 按照特性
    • 插入排序
      • 直接插入排序
      • 折半插入排序
      • 希尔排序
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 归并排序
    • 基数排序
• 适用性
  • 数据量大
    • 外部排序
  • 数据量不大
    • 内部排序
• 性能
  • 内部排序
    • 主要看时空复杂度
  • 外部排序
    • 主要看读写次数

插入排序

直接插入排序

• 代码
• 时空复杂度
• 稳定性

折半插入排序

• 代码
• 时空复杂度
• 稳定性

希尔排序

• 代码
• 时空复杂度
• 稳定性

直接插入排序（C语言）代码

void insert_sort(int *array, int n) {
	for (int i=2;i<=n;i++) {
		if (array[i]<array[i-1]) {
			array[0]=array[i];
			int j;
			for (j=i-1;array[j]>array[0];j--){
				array[j+1]=array[j];
			}
			array[j+1]=array[0];
		}
	}
}

折半插入排序（C语言）代码

void insert_sort_halfsearch(int *array, int n) {
	int i,j,low,high,midst;
	for (i=2;i<=n;i++){
		if (array[i]<array[i-1]){
			array[0]=array[i];
			low=1;
			high=i-1;
			while (low<=high){
				midst=(low+high)/2;
				if (array[midst]>array[0])
					high=midst-1;
				else
					low=midst+1;
			}
			for (j=i-1;j>=high+1;j--)
				array[j+1]=array[j];
			array[j+1]=array[0];
		}
	}
}

希尔排序（C语言）代码

void shell_sort(int *array, int n) {
	int i,j,dk;
	for (dk=n/2;dk>=1;dk=dk/2)
		for (i=dk+1;i<=n;i++)
			if (array[i]<array[i-dk]){
				array[0]=array[i];
				for (j=i-dk;j>0&&array[j]>array[0];j-=dk){
					array[j+dk]=array[j];
				}
				array[j+dk]=array[0];
			}
}

交换排序

冒泡排序

• 代码
• 时空复杂度
• 稳定性

快速排序

• 代码
• 时空复杂度
• 稳定性

冒泡排序（C语言）代码

void bubble_sort(int *array, int n) {
	for (int i=0;i<n-1;i++){
		int flag=0;
		for (int j=n-1;j>i;j--){
			if (array[j-1]>array[j]){
				int temp=array[j];
				array[j]=array[j-1];
				array[j-1]=temp;
				flag=1;
			}
		}
		if (!flag)
			return;
	}
}

快速排序（C语言）代码

int partition(int *array, int low, int high) {
	int pivot = array[low];
	while (low<high) {
		while (low<high&&array[high]>=pivot) high--;
		array[low]=array[high];
		while (low<high&&array[low]<=pivot) low++;
		array[high]=array[low];
	}
	array[low]=pivot;
	return low;
}

void quick_sort_func(int *array, int low, int high) {
	if (low<high) {
		int pivot_position=partition(array, low, high);
		quick_sort_func(array, low, pivot_position-1);
		quick_sort_func(array, pivot_position+1, high);
	}
}

void quick_sort(int *array, int n) {
	int low=0,high=n-1;
	quick_sort_func(array, low, high);
}

选择排序

简单选择排序

• 可用链表哦
• 代码
• 性能
• 稳定性

堆排序

• 从n/2开始建堆
• 插入
• 删除
• 大根堆堆顶堆底互换，调整剩下前n-i个元素，如此循环得到不减数列
• A[0]不用
• 性能
• 稳定性
• 固定堆长解决最大/最小m数问题

简单选择排序（C语言）代码

void simple_select_sort(int *array, int n) {
	for (int i=0;i<n-1;i++){
		int min_index = i;
		int j;
		for (j=i+1;j<n;j++){
			if (array[j]<array[min_index])
				min_index=j;
		}
		int temp=array[i];
		array[i]=array[min_index];
		array[min_index]=temp;
	}
}

归并排序和基数排序

归并排序

• 代码
• 性能
• 稳定性
• 改进：先用直接插入排序对自序列进行排序

基数排序

• 基你太稳

2路归并排序（C语言）代码

void merge(int *array, int low, int high) {
	int asist[high-low+1];
	int mid=(low+high)/2;
	int i=low,j=mid+1;
	while (i<=mid&&j<=high){
		if (array[i]<array[j]){
			asist[i-low+j-mid-1]=array[i];
			i++;
		} else{
			asist[i-low+j-mid-1]=array[j];
			j++;
		}
	}
	while (i<=mid){
		asist[i-low+j-mid-1]=array[i];
		i++;
	}
	while (j<=high){
		asist[i-low+j-mid-1]=array[j];
		j++;
	}
	for (int k=low;k<=high;k++)
		array[k]=asist[k-low];
}

void merge_sort_func(int *array, int low, int high){
	if (low<high){
		/* printf("low: %d, high: %d\n", low, high); */
		int mid=(low+high)/2;
		merge_sort_func(array, low, mid);
		merge_sort_func(array, mid+1, high);
		merge(array, low, high);
		/* print_array(array+low, high-low+1); */
	}
}

void merge_sort(int *array, int n) {
	int low=0,high=n-1;
	merge_sort_func(array, low, high);
}