数据结构 | 第九章排序

亦凉 2022-09-03 02:25 239阅读 0赞

### 文章目录 ###

*   *   *  一、排序
         *   *  1、概念以及分类
             *   *  1.1 排序的稳定性
                 *  1.2 内排序和外排序
                 *   *  1.2.1 时间性能
                     *  1.2.2 辅助空间
                 *  1.3 排序的结构与函数
             *  2、简单算法
             *   *  2.1 冒泡排序
                 *  2.2 选择排序
                 *  2.3 直接插入排序
             *  3、改进算法
             *   *  3.1 希尔排序
                 *  3.2 堆排序
                 *  3.3 归并排序
                 *  3.4 快速排序

### 一、排序 ###

#### 1、概念以及分类 ####

>  *  使得序列成为一个`按关键字有序`的序列；
>  *  记录：排序中称数据元素；

##### 1.1 排序的稳定性 #####

> 排序前r1先于r2，排序后r1仍领先r2则该方法`稳定`。

##### 1.2 内排序和外排序 #####

**内排序**：

> 整个排序过程中，待排序的所有记录全被放置再内存中；

>  *  插入排序
>  *  交换排序
>  *  选择排序
>  *  归并排序

**外排序**：

> 记录太多，不能同时放置在内存中，排序过程需要不断进行内外存交换。

###### 1.2.1 时间性能 ######

> 排序主要操作是`比较`以及`移动`。所以要想提高效率，必定要减少这些操作的次数。

###### 1.2.2 辅助空间 ######

> 评价该算法的其他标准就是执行算法的辅助存储空间。

##### 1.3 排序的结构与函数 #####

#define MAXSIZE 10
    
    typedef struct{ 
    	int r[MAXSIZE+1];	// r[0]存储临时变量
    	int length;
    };
    
    /*@ 数组间的俩元素交换 */
    void swap(SqList *L, int i, int j){ 
    	int temp = L->r[i];
    	L->r[i] = L->r[j];
    	L->r[j] = temp;
    }

#### 2、简单算法 ####

##### 2.1 冒泡排序 #####

>  *  俩俩比较的关键字，若反序则交换；

void BubbleSort(SqList *L){ 
    	int i,j;
    	for(i=1; i<L->length;i++){ 
    		for(j=i+1; j<L=->length; ++j){ 
    			if(L->r[i]>L-<r[j]){ 
    				swap(L, i, j);
    			}
    		}
    	}
    }
    
    
    /*@ 改进后 */
    void BubbleSort_(SqList *L){ 
    	int i,j;
    	for(i=1; i<L->length;i++){ 
    		for(j=L=->length-1; j>=i; --j){ 
    			if(L->r[j]>L-<r[j+1]){ 
    				swap(L, j, j+1);
    			}
    		}
    	}
    }
    
    /*@ 优化，添加flag * 避免在有序的情况下无意义循环 */
    void BubbleSort_(SqList *L){ 
    	int i,j, flag = 1;
    	for(i=1; i<L->length && flag ;i++){ 
    		flag = 0;
    		for(j=L=->length-1; j>=i; --j){ 
    			if(L->r[j]>L-<r[j+1]){ 
    				swap(L, j, j+1);
    				flag = 1;
    			}
    		}
    	}
    }

> 最好时间复杂度：`O(n)`；最坏时间复杂度：`O(n^2)`。

##### 2.2 选择排序 #####

> 通过`n-i`次关键字比较，从`n-i+1`个记录中选出关键字`最小`的记录，并和第i个交换。

void SelectSort(SqList *L){ 
    	int i,j,min;
    	for(i=1; i<L->length; ++i){ 
    		min = i;	// 当前下标为最小的下标
    		for(j=i+1; j<=L->length; ++j){ 
    			if(L->r[min]>L->r[j]){ 
    				min = j;	// 判断值是否比min下标的小
    			}
    			if(i!=min){ 
    				swap(L, i, min);	
    			}
    		}
    	}
    }

>  *  特点：`移动次数`较少。
>  *  时间复杂度：`O(n)`；
>  *  性能要优于冒泡排序。

##### 2.3 直接插入排序 #####

> 将记录插入到已经`排好序`的有序表中。

void InsertSort(SqList *L){ 
    	int i,j;
    	for(i=2; i<L->length; ++i){ 
    		if(L->r[i] < L->r[i-1]){ 
    			L->r[0] = L->r[i];	// 设置哨兵
    			for(j=i-1; L->r[j]>L->r[0]; j--){ 
    				L->r[j+1] = L->r[j];
    			L->r[j+1] = L->r[0];
    			}	
    		}
    	}
    }

>  *  空间上只需要记录的辅助空间；
>  *  时间复杂度：`O(n^2)`；
>  *  性能比冒泡和排序要好。

#### 3、改进算法 ####

##### 3.1 希尔排序 #####

> 对插入排序进行改进。对大量记录分组，子序列排序后在进行插入排序。

>  *  基本排序：`小在前，大在后，不大不小在中间`。
>  *  跳跃分割策略：将相距某个增量的记录组成一个子序列，保证子序列内分别进行直接插入排序后`基本有序`而不是局部有序。

void ShellSort(SqList *L){ 
    	int i,j;
    	int increment = L->length;
    	do{ 
    		increment = increment /3 + 1;	// 增量序列
    		for(i=increment + 1;i<=L->length; i++){ 
    			if(L->r[i]<L->r[increment]){ 
    				L->r[0] = L->r[i];	// 暂存在L->r[0]
    				for(j=i-increment l j>0&&L->r[0]<L->r[j];j-=increment){ 
    					L->r[j+increment] = L->r[j];	
    				}
    				L->r[j+increment] = L->r[0];
    			}
    		}
    	}while(increment>1);
    }

>  *  时间复杂度：`O(n^3/2)`；
>  *  注意：增量序列的最后一个增量值必须为1。

##### 3.2 堆排序 #####

**堆具有完全二叉树的性质**：

>  *  大顶堆：每个结点的值都`大于或等于`其左右孩子结点的值；
>  *  小顶堆：或者每个结点的值都`小于或等于`其左右孩子结点的值。

**基本思想**：

> 将序列构成一个大顶堆，整个序列的`最大值就是堆顶的根结点`。`将它移走`，后将剩余的n-1个序列构成一个堆，在反复执行。

void HeapAdjust(SqList *L, int s, int m){ 
    
    	int temp, j;
    	temp = L->r[s];
    	for (j = 2 * s; j <= m; j *= 2){ 
    		if (j < m && L->r[j] < L->r[j + 1]){ 
    			++j;
    		}
    		if (temp >= L->r[j])
    			break;
    		L->r[s] = L->r[j];
    		s = j;
    	}
    	L->r[s] = temp;
    }
    
    /* 第一次循环构建大顶堆； 第二次每个最大值的根节点与末尾元素交换。 【从上往下、从左往右】 */
    void HeapSort(SqLits *L){ 
    	int i;
    	for (i = L->length / 2; i > 0; --i){ 
    		HeapAdjust(literal, i, L->length);
    	}
    	for (i = L->length; i > 1; --i){ 
    		swap(L, 1, i);
    		HeapAdjust(L, 1, i - 1);
    	}
    }

>  *  构建时间复杂度：第i次要`O(logi)`；
>  *  重建时间复杂度：`O(nlogn)`；
>  *  不适合待排序序列个数较少的情况。

##### 3.3 归并排序 #####

**2路归并排序**：

> n个有序的子序列，每个子序列长度为1，后俩俩合并，得到\[`n/2`\]个长度为2或1的有序子序列；在俩俩归并，重复循环。

void HeapSort(SqLits *L){ 
    	int i;
    	for (i = L->length / 2; i > 0; --i){ 
    		HeapAdjust(literal, i, L->length);
    	}
    	for (i = L->length; i > 1; --i){ 
    		swap(L, 1, i);
    		HeapAdjust(L, 1, i - 1);
    	}
    }
    
    void MergeSort(SqLits *L){ 
    	MSort(L->r, L->r, L->length);
    }
    
    void Merge(int SR[], int TR[], int i, int m, int n){ 
    	int j, k, l;
    	for (j = m + 1, k = i; i <= m && j <= n; ++k){ 
    		if (SR[i] < SR[j])
    			TR[k] = SR[i++];
    		else
    		{ 
    			TR[k] = SR[j++];
    		}
    	}
    	if (i < m){ 
    		for (l = 0; l <= m - i; l++)
    			TR[k + 1] = SR[i + 1];
    	}
    	if (j <= n){ 
    		for (l = 0; l <= n - j; l++)
    			TR[k + l] = SR[j + l];
    	}
    }
    
    /*@ 非递归实现归并排序 */
    void MergeSort2(SqList *L){ 
    	int *TR = (int *)malloc(L->length * sizeof(int));
    	int k = 1;
    	while (k<L->length)
    	{ 
    		MergePass(L->r, k, L->length);
    		k = 2 * k;
    		MergePass(TR, L->r, k, L->length);
    		k = 2 * k;
    	}
    }
    
    void MergePass(int SR[], int TR[], int s, int n){ 
    	int i = 1;
    	int j;
    	while (i < n-2*s+1)
    	{ 
    		Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
    		i = i + 2 * s;
    	}
    	if (i < n - s + 1){ 
    		Merge(SR, TR, i, i + s - 1, n);
    	}
    	else
    	{ 
    		for (j = i; j <= n; ++j){ 
    			TR[j] = SR[j];
    		}
    	}
    }

>  *  总时间复杂度：`O(nlogn)`；
>  *  空间复杂度：`O(n+logn)`；
>  *  比较`占内存`，但`效率高且稳定`。

##### 3.4 快速排序 #####

> 通过一趟排序将待排记录`分割成独立`的俩部分，其中`一部分的关键字均比另一部分小`，可分别对这俩部分记录继续进行排序。

void Partition(SqList *L, int low, int high){ 
    	int pivotkey;
    	pivotkey = L->r[low];
    	while(low < high){ 
    		while(low<high && L->r[high]>=pivotkey)
    			high--;
    		swap(L, low, high);
    		while(low<high && L->r[low] <= pivotkey)
    			low++;
    		swap(L, low, high);
    	}
    	return low;
    }
    
    void QSort(SqList *L, int low, int high){ 
    	int pivot;
    	if(low < high){ 
    		pivot = Partition(L, low, high);
    		QSort(L, low, pivot-1);
    		QSort(L, pivot+1, gigh);
    	}
    }

>  *  最优时间复杂度：`O(nlogn)`；取决于递归的深度。
>  *  平均空间复杂度：`O(logn)`；

**优化快排**

>  *  三数取中；
>  *  九数取中；分三次三数取中