数据结构(7) 排序

插入排序

直接插入排序

把$n$个待排序的元素假设为一个有序表和一个无序表，开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次即可完成排序过程

1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(int array[],int n) {
	int i, j, key;
	for (i = 1; i < n; i++) {
		if (array[i] < array[i - 1]) {
			key = array[i];//设置为哨兵
            //找到合适的插入位置并将比key大的元素后移
			for (j = i - 1; key < array[j] && j >= 0; --j)
				array[j + 1] = array[j];
			array[j + 1] = key;//插入
		}
	}
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertSortbyHalf(int array[],int n){
    int i,j,key,mid,low,high;
    for (i = 1; i < n; i++) {
        if(array[i] < array[i-1]){
            key = array[i];
            low = 0,high = i-1;
          	//找到插入的位置
            while(low <= high){
                mid = (low + high) / 2;
                if(key < array[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
          	//统一移动元素
            for(j = i-1;j >= high+1;j--){
                array[j+1] = array[j];
            }
            array[j+1] = key;//插入
        }
    }
}

希尔排序

增量序列 $d1，d_2，\cdots，d_k$，其中 $d_1=n/2,d{i+1}=[d_i/2],d_k = 1$；

按增量序列个数 $k$，对序列进行 $k$ 趟排序；

每趟排序，先根据对应的增量 $d_i$，将待排序序列分割为$d_i$个组，距离为$d_i$的元素为同一组，再对每个组进行直接插入排序，直到$d_i =1$,即所有元素已在同一组中，再进行一次直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void shellSort(int array[],int n) {
	int di, i,j, key;
	for (di = n/2; di >= 1; di = di/2) {//设置增量
        //分组并进行插入排序
		for (i = di; i < n; i++) {
			if (array[i] < array[i - di]) {
				key = array[i];
				for (j = i - di; j >= 0 && key < array[j]; j = j - di) {
					array[j + di] = array[j];
				}
				array[j + di] = key;
			}
		}
	}
}

交换排序

冒泡排序

每次比较两个相邻的元素，如果其顺序错误就交换

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(int array[],int n) {
	int key;
	for (int i = 0; i < n-1;i++) {
		//LEN-i:每一次都已归位一个数,不再需要与已归位的数比较
		for (int j = 0; j < n - i - 1; j++) {
			if (array[j] > array[j + 1]) {
				key = array[j];
				array[j] = array[j + 1];
				array[j + 1] = key;
			}
		}
	}
}

快速排序

1.设置两个变量$i,j$，初始化：$i=0，j=n-1$；
2.基准数 $key=array[0]$ ；
3.从 $j$ 开始向前搜索，即由后开始向前搜索 $(j—)$ ，找到第一个小于 $key$ 的值 $array[j]$ ，将 $array[j]$ 和 $array[i]$ 的值交换；
4.从 $i$ 开始向后搜索，即由前开始向后搜索 $(i++)$ ，找到第一个大于key的 $array[i]$ ，将 $array[i]$ 和 $array[j]$ 的值交换；
5.重复第3、4步，直到 $i=j$ ；

经过一趟上述步骤后，基准数左边全小于基准数，基准数右边全大于基准数，通过分治法继续处理左、右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void quickSort(int array[], int left, int right){
	if (left >= right){
		return;
	}
	int i = left;
	int j = right;
	int key = array[left];//基准数

	while (i < j){
        //向前寻找小于key的数
		while (i < j && key <= array[j]){
			j--;
		}
		array[i] = array[j];
        //向后寻找大于key的数
		while (i < j && key >= array[i]){
			i++;
		}
		array[j] = array[i];
	}
	array[i] = key;//基准数归位
	quickSort(array, left, i - 1);//分治处理左边
	quickSort(array, i + 1, right);//分治处理右边
}

选择排序

简单选择排序

(1)在未排序序列中找到最小/大元素，存放到排序序列的起始位置;(2)再从剩余未排序元素中继续寻找最小/大元素，放到已排序序列的末尾;重复第二步，直到所有元素均排序完毕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort(int array[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int min = i;
		for (int j = i + 1; j < n; j++) {
			if (array[j] < array[min])
				min = j;
		}
		if (i != min) {
			int temp = array[i];
			array[i] = array[min];
			array[min] = temp;
		}
	}
}

堆排序

堆是具有以下性质的完全二叉树：

1.每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

2.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆；

堆排序算法步骤：

1.构造初始堆，将无序序列构造为大顶堆，从倒数第一个非叶子结点开始调整,从左至右，从下至上进行调整；

倒数第$i$个非叶子结点索引$index=array.length/2^i-1(i=1,2,3\dots|2^i\leqslant array.length)$

2.将堆顶元素与末尾元素进行交换，使末尾元素最大，然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素，如此反复进行交换、重建、交换…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void swap(int* a, int* b){
	int temp = *b;
	*b = *a;
	*a = temp;
}

void max_heapify(int array[], int start, int end){
	//建立父节点指标和子结点指标
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end){//若子结点索引在范围内才做比较
		//先比较两个子结点大小，选择最大的
		if (son + 1 <= end && array[son] < array[son + 1])
			son++;
		if (array[dad] > array[son]) //如果父节点大於子结点代表调整完毕，直接跳出函数
			return;
		else{
			swap(&array[dad], &array[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(int array[], int len){
	int i;
	//初始化，生成最大堆
	for (i = len / 2 - 1; i >= 0; i--)
		max_heapify(array, i, len - 1);

	//堆顶元素与末尾元素进行交换，再重新调整，直到排序完毕
	for (i = len - 1; i > 0; i--){
		swap(&array[0], &array[i]);
		max_heapify(array, 0, i - 1);
	}
}

归并排序

假定含有$n$个元素的待排序表，则可视为$n$个有序的子表，每个子表长度为1，然后两两归并，得到[$n/2$]个长度为2或1的有序表；再两两归并$\cdots$,直到合并长度为$n$的有序表为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void merge(int array[], int low, int mid, int high, int temp[]){
	int i = low, j = mid + 1;
	int m = mid, n = high;
	int k = 0;
	while (i <= m && j <= n){
		if (array[i] <= array[j])
			temp[k++] = array[i++];
		else
			temp[k++] = array[j++];
	}
	while (i <= m)
		temp[k++] = array[i++];

	while (j <= n)
		temp[k++] = array[j++];

	for (i = 0; i < k; i++)
		array[low + i] = temp[i];
}
void mergesort(int array[], int low, int high, int temp[]){
	if (low < high){
		int mid = (low + high) / 2;
		mergesort(array, low, mid, temp);    
		mergesort(array, mid + 1, high, temp); 
		merge(array, low, mid, high, temp);
	}
}

数据结构
#数据结构
数据结构(7) 排序
https://jiaopaner.github.io/2019/07/19/数据结构(7) 排序/
作者
JiaoPan
发布于
2019年7月19日
许可协议