几种排序算法的实现-蒲公英云

几种排序算法的实现

插入排序

直接插入排序

//对数组int A[n]进行直接插入排序
void InsertSort(int A,int n){

int j,temp;
for(int i=1;i<n;i++){
    temp=A[i];//将当前待排序的元素存储在temp中
    j=i-1;//从当前待排元素的前一个元素开始扫描数组
    while(j>=0&&A[j]>temp){
        A[j+1]=A[j];
        j--;
    }
    R[j+1]=temp;//完成下标为i的元素的排序
}

}

折半插入排序

//对数组A[n]进行折半插入排序
void InsertSort(int A[],int n){

int temp,low,high,mid
for(int i=1;i<n;i++){
    temp=A[i];//将当前待排序元素存储到temp中
    low=0;high=i-1;
    while(low<=high){
//通过折半查找，找到待排序元素应该插入的位置为high+1;
        mid=(low+high)/2;
        if(A[mid]>temp) low=mid+1;
        else high=mid-1;
    }//折半查找结束
    //移动元素
    for(j=i;j>high+1;j--){
        A[j]=A[j-1];
    }
    A[j]=temp;//将下标为i的元素排好序
}

}

交换排序

冒泡排序

//对数组A[n]进行冒泡排序
void BubbleSort(int A[],int n){

bool flag;
for(int i=0;i<n-1;i++){
//n个元素最多进行n-1趟排序
    flag=false;
    for(int j=0;j<n-i-1;j++){
        if(A[j]>A[j+1]){
            swap(A[j],A[j+1]);//按照从大到小的顺序排列
            flag=true;
        }
    }
    if(flag==false) return;//如果某一趟冒泡结束，未发生交换，说明数组中的元素已经实现有序排列
}

}

快速排序

在待排序的列表中选择一个元素作为基准pivot，通过一趟排序将待排序表划分为两部分，一部分元素小于pivot,另一部分元素大于pivot,此时pivot放在了其最终位置上。而后递归的对其子表重复上述过程

void QuickSort(int R[],int low,int high){

int pivot,i,j;
i=low;j=high;
if(low<high){
    pivot=R[low];
    while(i!=j){
        while(j>i&&R[j]>pivot;j--)//从右向左
        if(j>i){
            R[i]=R[j];
            i++;
        }
        while(i<j&&R[i]<pivot;i++)//从左向右
        if(i<j){
            R[j]=R[i];
            j--;
        }
    }//当i=j,循环结束
    R[i]=pivot;//pivot最终位置确定
    QuickSort(R,low,i-1);
    QuickSort(R,i+1;high);
}

}

选择排序

简单选择排序

每一趟排序，找到待排序列中的最小元素，与该代派序列的第一个元素交换位置

void SeleteSort(int A[],int n){

int i;j;k;
for(i=0;i<n;i++){
    k=i;
    for(j=i+1;j<n;j++){
 //寻找带排序列最小元素的下标
        if(A[j]<A[k])
            k=j;
    }
    swap(A[k],A[i]);
}

}

设有一个数组为a1,a2…an，现要求将an放在排序后正确的位置上，实现该算法

//使用快速排序，将an作为枢轴量
void Sort(int A[],int low,int high){

int i=low,j=high;
int pivot;
if(i>=j) return;
while(i!=j){
    pivot=A[j];
    while(i<j&&A[i]<pivot)
        i++;
    if(i<j){
        A[j]=A[i];
        j--;
    }
    while(i<j&&A[j]>pivot)
        j--;
    if(i<j){
        A[i]=A[j];
        i++;
    }
}
A[i]=pivot;

}

输入一个整数数组，调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分

奇数和奇数、偶数和偶数之间的相对位置可变

//使用快速排序
void Sort(int A[],int low,int high){

int i=low,j=high;
int pivot;
if(i>=j) return;
while(i!=j){
    pivot=A[i];
    while(i<j&&A[j]%2==0)
        j--;
    if(i<j){
        A[i]=A[j];
        i++;
    }
    while(i<j&&A[i]%2==1)
        i++;
    if(i<j){
        A[j]=A[i];
        j--;
    }
}//while
A[i]=pivot;

}

奇数奇数、偶数偶数之间的相对位置不可变

//方法一：使用冒泡排序
void Sort(int A[],int n){

//如果是前偶后奇则交换位置
bool flag;
for(int i=0;i<n-1;i++){
    for(int j=0;j<n-1-1;j++){
        if(A[j]%2==0&&A[j+1]%2==1){
            temp=A[j];
            A[j]=A[j+1];
            A[j+1]=temp;
            flag=true;
        }
    }//for
    if(flag==false) return;
}//for

}

//方法二：创建辅助数组
void Sort(int A[],int n){

int a[n],int b[n];
int j=0,k=0;
for(int i=0,i<n;i++){
    if(A[i]%2==0){
        a[j++]=A[i];
    }else{
        b[k++]=A[i];
    }
}
int t=0;
for(;j<n;j++){
    a[j]=b[t];
    t++;
}

}

带头结点的双向链表，对其进行双向起泡法升序排列

bool doublebubbleSort(DLinkList &L){

DLinkList *p,*q=NULL;
bool flag=true;
while(flag==true){
    p=L->next;
    flag=false;
    while(p->next!=q){
        if(p->data>p->next->data){
            swap(p->data,p->next-data);
            flag=true;
        }
        p=p->next;
    }//while
    q=p;
    p=q->prior;
    while(p->prior!=L){
        if(p->data<p->prior->data){
            swqp(p->data,p->prior->data);
            flag=true;
        }
        p=p->prior;
    }//while
    L=p;//下次起泡的起点
}