排序 | xunyue

折半插入排序

思路：先用折半查找找到应该插入的位置，再移动元素；

为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该继续在这个元素的右半部分继续查找以确认位置; 即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置

当low>high时，折半查找停止，应将[low,i-1]or[high+1,i-1]内的元素全部右移，并将A[0]复制到low所指的位置；

代码实现

void InsertSort(int A[], int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){
A[0] = A[i]; //将A[i]暂存到A[0]
low = 1; high = i-1; //折半查找的范围

    while(low<=high){               //折半查找
        mid = (low + high)/2;       //取中间点
        if(A[mid]>A[0])             //查找左半子表
            high = mid - 1;
        else                        //查找右半子表
            low = mid + 1;
    }
    
    for(j=i-1; j>high+1;--j)       //统一后移元素，空出插入位置
        A[j+1] = A[j];
    A[high+1] = A[0]
}

}

希尔排序

思路：先追求表中元素的部分有序，再逐渐逼近全局有序；

更适用于基本有序的排序表和数据量不大的排序表，仅适用于线性表为顺序存储的情况

代码实现：

void ShellSort(ElemType A[], int n){
//A[0]为暂存单元
for(dk=n/2; dk>=1; dk=dk/2) //步长递减（看题目要求，一般是1/2
for(i=dk+1; i<=n; ++i)
if(A[i]<A[i-dk]){
A[0]=A[i];
for(j=i-dk; j>0&&A[0]<A[j];j-=dk)
A[j+dk]=A[j]; 记录后移，查找插入的位置
A[j+dk]=A[0;] 插入
}
}

冒泡排序

略

快速排序

每一趟排序都可使一个中间元素确定其最终位置
用一个元素（不一定是第一个）把待排序序列“划分”为两个部分，左边更小，右边更大，该元素的最终位置已确认
算法实现（重点）
//用第一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){
int pivot = A[low]; //用第一个元素作为枢轴
while(low<high){
while(low < high && A[high]>=pivot) –high; //high所指元素大于枢轴，high左移
A[low] = A[high]; //high所指元素小于枢轴，移动到左侧

    while(low<high && A[low]<=pivot)  ++low; //low所指元素小于枢轴，low右移
    A[high] = A[low];   //low所指元素大于枢轴，移动到右侧
}
A[low] = pivot   //枢轴元素存放到最终位置
return low；     //返回存放枢轴的最终位置

}

//快速排序
void QuickSort(int A[], int low, int high){
if(low<high) 递归跳出条件
int pivotpos = Partition(A, low, high); 划分
QuickSort（A, low, pivotpos - 1); 划分左子表
QuickSort（A, pivotpos + 1, high); 划分右子表
}

简单选择排序

void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}

void SelectSort(int A[], int n){ //A从0开始
for(int i=0; i<n-1; i++){ 一共进行n-1趟，i指向待排序序列中第一个元素
int min = i; 记录最小元素位置
for(int j=i+1; j<n; j++) 在A[i…n-1]中选择最小的元素
if(A[j] <> A [min]) min = j; // 更新最小元素位置
if(min!=i)
swao(A[i],A[min]); // 交换
}
}

归并排序

把两个或多个已经有序的序列合并成一个
//创建辅助数组B
int *B=(int )malloc(nsizeof(int));

//A[low,…,mid],A[mid+1,…,high] 各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++)
B[k] = A[k]; //将A中所有元素复制到B中
for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
if(B[i]<=B[j]) //为保证稳定性两个元素相等时，优先使用靠前的那个
A[k]=B[i++]; //将较小值复制到A中
else
A[k]=B[j++];
}//for

//没有归并完的部分复制到尾部，while只会执行一个 
while(i<=mid)  A[k++]=B[i++];     //若第一个表未检测完，复制
while(j<=high) A[k++]=B[j++];     //若第二个表未检测完，复制

}

//递归操作
void MergeSort(int A[], int low, int high){
if(low<high){
int mid = (low+high)/2; 从中间划分
MergeSort(A, low, mid); 对左半部分归并排序
MergeSort(A, mid+1, high); 对右半部分归并排序
Merge(A,low,mid,high); 归并
}if
}