排序算法学习笔记_随笔

排序算法学习笔记

一、冒泡排序

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

三种不同的冒泡实现

1.不算是标准的冒泡排序算法，不满足“两两交换相邻记录”的冒泡排序思想

思路：让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。

缺陷：在排序好1和2的位置后，对其余关键字的排序没有什么帮助（数字3反而还被换到了最后一位）。

2.正宗的冒泡排序算法

思路：每一次都从最后一个位置开始往前两两比较，前一个大于后一个则交换，第一次会把最小的关键字交换到第一个位置，第二次把第二小的关键字交换到第二个位置，，，如此往复。排序完成。

缺陷：如果待排序的序列是{2,1,3,4,5,6,7,8,9}，那么除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1，此时序列已经有序，但是算法却还会继续执行i=2到9以及每个循环中的j循环

3.优化后的冒泡排序

思路：增加一个标记变量flag，记录一趟下来是否有交换发生

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}


//三种冒泡排序
//简单冒泡排序
void BubbleSort0(SqList *L){
    for(int i=1;ilength-1;i++){
        for(int j=i+1;j<=L->length;j++){
            if(L->r[i]>L->r[j])
                swap(L,i,j);
        }
    }
}


//正宗冒泡排序
void BubbleSort(SqList *L){
    for(int i=1;ilength;i++){
        for(int j=L->length-1;j>i;j--){
            if(L->r[j+1]r[j])
                swap(L,j,j+1);
        }
    }
}


//优化冒泡排序
void BubbleSort1(SqList *L){
    static bool flag=true;
    for(int i=1;ilength&&flag;i++){
        flag=false;
        for(int j=L->length-1;j>i;j--){
            if(L->r[j+1]r[j])
                swap(L,j,j+1);
                flag=true;
        }
    }
}

二、选择排序

简单选择排序（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}


//简单选择排序
void SelectSort(SqList *L){
    int i, j, min;
    for(i=1;ilength;i++){
        min=i;
        for(j=i+1;j<=L->length;j++){
            if(L->r[j]r[min])
                min=j;
        }
        if(i!=min)
            swap(L,i,min);
    }
}

三、插入排序

直接插入排序（Straight Insertion Sort）的基本 *** 作时将一个记录插入到已经排好序到有序表中，从而得到一个新的、记录数增1的有序表。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}


//直接插入排序
void InsertSort(SqList *L){
    int i,j;
    for(i=2;i<=L->length;i++){
        if(L->r[i]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];
        }
    }
}

插入排序在两种情况下效率是很高的：

1.记录本身就是基本有序的，只需要少量的插入 *** 作，就可以完成整个记录的排序工作，此时直接插入很高效。

2.记录数较少时，直接插入的优势也比较明显。

四、希尔排序

希尔排序（Shell Sort）的主要思想就是创造出以上两个条件进行直接插入排序。可以说希尔排序就是通过以下两个策略进行优化后的插入排序：

1.将原本有大量记录数的记录进行分组。对分组进行直接插入排序。

2.分组策略的选择就是最终的记录集是否基本有序的关键。在这里我们采取跳跃分割的分组策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。在整个希尔排序过程中存在一个增量序列且增量序列的最后一个增量值必须等于1，在进行最后一趟增量值为1的直接插入排序之前，原序列集已达成基本有序的要求。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//希尔排序
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]r[i-increment]){
        L->r[0]=L->r[i];
        for(j=i-increment;j>0&&L->r[0]r[j];j-=increment){
          L->r[j+increment]=L->r[j];
        }
        L->r[j+incremnet]=L->r[0];
      }
    }
  }while(increment>1);
}

五、堆排序

堆（heap）是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

从这里的定义可以看出根结点一定是堆中所有结点最大（小）者。这是实现堆排序的前提。

按照层序遍历的序号将堆的结点的值存入数组，起始序号为1。双亲结点序号为k时，左孩子结点序号为2*k，右孩子结点序号为2*k+1。结点总数为n时，最后一个有孩子的结点序号为n/2 。

堆排序（Heap Sort）的主要思想就是先将待排序的序列构造成一个大顶堆，然后交换其根结点和最后一个结点，此时最后一个结点变成了最大值；接着维护第一个结点使剩下的n-1个结点变成大顶堆，同样交换根结点和最后一个结点，此时最后一个结点变成了剩下的n-1个结点的最大值，也是所有结点的次大值；如此循环直至最后所有结点都变得有序。

其中维护大顶堆是整个思想的核心：被交换到首位的结点即是我们需要维护的结点，先找到该结点与其左右孩子结点中的最大值的位置，交换该结点与最大值位置结点，递归维护最大值位置结点。

简单来说，只要交换了两个结点，就需要维护使其仍然是大顶堆。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//堆的维护，i是结点的序号
void HeapFit(SqList *L,int i){
    int largest=i;
    int lson=i*2;
    int rson=i*2+1;
    
    if(L->r[largest]r[lson])
        largest=lson;
    if(L->r[largest]r[rson])
        largest=rson;
    if(largest!=i){
        swap(L,largest,i);
        HeapFit(L,largest);
    }
}


//堆排序
void HeapSort(SqList *L){
    int i;
    int temp=L->length;//保存L->length的初值
    
    //建堆，从最后一个有孩子的结点开始维护
    for(i=L->length/2;i>0;i--){
        HeapFit(L,i);
    }
    
    //堆排序
    for(i=L->length;i>1;i--){
        swap(L,1,i);
        L->length--;
        HeapFit(L,1);
    }
    L->length=temp;
}

六、归并排序

归并排序（Merging Sort）的主要思想是划分与归并。首先将一个序列递归二分划分，最后划分成n个单个的有序序列，然后再按划分时候的路径归并回去。重点在归并的时候是对两个已排好序的有序序列进行归并得到一个有序序列，归并时因为两个序列已经分别有序，所以只需设置两个指向头元素的指针，进行比较将较小值放入临时数组，然后较小值指针和临时数组指针同时加一，重复此 *** 作，最后两个有序序列中剩余的元素直接复制到临时数组即可。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;


//归并排序
//归并的实现
void Merge(SqList *L,int tempL[],int left,int mid,int right){
    int l_pos=left;
    int r_pos=mid+1;
    int pos=left;
    while(l_pos<=mid&&r_pos<=right){
        if(L->r[l_pos]r[r_pos])
            tempL[pos++]=L->r[l_pos++];
        else
            tempL[pos++]=L->r[r_pos++];
    }

    while(l_pos<=mid)
        tempL[pos++]=L->r[l_pos++];
    while(r_pos<=right)
        tempL[pos++]=L->r[r_pos++];
    
    while(left<=right){
        L->r[left]=tempL[left];
        left++;
    }
}



//划分
void MSort(SqList *L,int tempL[],int left,int right){
    if(leftlength;
    if(tempL){
        MSort(L,tempL,1,n);
    }
}

七、快速排序

快速排序的主要思想是先在待排序序列中选出一个关键字，然后想办法将它放到一个位置使得它左边的值都比它小，右边的值都比它大，我们把这样的关键字称为枢轴。然后再对其左右两边的序列再递归做同样的 *** 作。那么如何将枢轴放到对应的位置就是该算法的关键：首先使用两个指针i，j指向每一次待排序序列的第一个位置，指针pivot指向最后一个位置，j遍历序列的序号，如果j指向的值小于pivot指向的值就将i和j指向的值交换并且i加加，到最后i指向的就是序列中第一个比pivot指向的值大的位置，最后交换i指向的值和pivot指向的值，就使得枢轴处在了自己对应的位置即 i。

#define MAXSIZE 10

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;


//快速排序
//寻找枢轴的正确位置
int partition(SqList *L,int low,int high){
    int i,j,pivot;
    i=low;
    pivot=high;
    for(j=i;jr[j]r[pivot]){
            swap(L,i,j);
            i++;
        }
    }
    swap(L,i,high);
    return i;
}

//递归对枢轴两边的序列进行排序
void QSort(SqList *L,int low,int high){
    if(lowlength);
}

八、总结验证：冒泡最慢；选择和插入次之（选择大概是插入的两倍）；希尔、堆、归并、快速更快（四者速度相当）。

#include
#include


using namespace std;

//MAXSIZE表示待排序列的长度
#define MAXSIZE 100000

typedef struct{
    int r[MAXSIZE+1];
    int length;
}SqList;

//交换序列中i位置和j位置的值
void swap(SqList *L,int i,int j){
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//打印序列
void print_SqList(SqList *L){
    int i;
    for(i=1;i<=L->length;i++)
        cout<r[i]<<" ";
}

//初始化序列
void CreatList(SqList *L){
    L->length=MAXSIZE;
    L->r[0]=0;
    for(int i=1;i<=L->length;i++){
        L->r[i]=rand()%MAXSIZE;
    }
}


//三种冒泡排序
//简单冒泡排序
void BubbleSort0(SqList *L){
    for(int i=1;ilength-1;i++){
        for(int j=i+1;j<=L->length;j++){
            if(L->r[i]>L->r[j])
                swap(L,i,j);
        }
    }
}


//正宗冒泡排序
void BubbleSort(SqList *L){
    for(int i=1;ilength;i++){
        for(int j=L->length-1;j>=i;j--){
            if(L->r[j+1]r[j])
                swap(L,j,j+1);
        }
    }
}


//优化冒泡排序
void BubbleSort1(SqList *L){
    static bool flag=true;
    for(int i=1;ilength&&flag;i++){
        flag=false;
        for(int j=L->length-1;j>i;j--){
            if(L->r[j+1]r[j])
                swap(L,j,j+1);
                flag=true;
        }
    }
}



//简单选择排序
void SelectSort(SqList *L){
    int i, j, min;
    for(i=1;ilength;i++){
        min=i;
        for(j=i+1;j<=L->length;j++){
            if(L->r[j]r[min])
                min=j;
        }
        if(i!=min)
            swap(L,i,min);
    }
}


//直接插入排序
void InsertSort(SqList *L){
    int i,j;
    for(i=2;i<=L->length;i++){
        if(L->r[i]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];
        }
    }
}


//希尔排序
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]r[i-increment]){
                L->r[0]=L->r[i];
                for(j=i-increment;j>0&&L->r[0]r[j];j-=increment)
                    L->r[j+increment]=L->r[j];
                L->r[j+increment]=L->r[0];
            }
        }
    }
    while(increment>1);
}


//堆的维护，i是结点的序号
void HeapFit(SqList *L,int i){
    int largest=i;
    int lson=i*2;
    int rson=i*2+1;
    
    if(lson<=L->length&&L->r[largest]r[lson])
        largest=lson;
    if(rson<=L->length&&L->r[largest]r[rson])
        largest=rson;
    if(largest!=i){
        swap(L,largest,i);
        HeapFit(L,largest);
    }
}

//堆排序
void HeapSort(SqList *L){
    int i;
    int temp=L->length;//保存L->length的初值
    //建堆，从最后一个有孩子的结点开始维护
    for(i=L->length/2;i>0;i--){
        HeapFit(L,i);
    }
    //堆排序
    for(i=L->length;i>1;i--){
        swap(L,1,i);
        L->length--;
        HeapFit(L,1);
    }
    L->length=temp;
}




//归并排序
//归并
void Merge(SqList *L,int tempL[],int left,int mid,int right){
    int l_pos=left;
    int r_pos=mid+1;
    int pos=left;
    while(l_pos<=mid&&r_pos<=right){
        if(L->r[l_pos]r[r_pos])
            tempL[pos++]=L->r[l_pos++];
        else
            tempL[pos++]=L->r[r_pos++];
    }

    while(l_pos<=mid)
        tempL[pos++]=L->r[l_pos++];
    while(r_pos<=right)
        tempL[pos++]=L->r[r_pos++];
    
    while(left<=right){
        L->r[left]=tempL[left];
        left++;
    }
}



//划分
void MSort(SqList *L,int tempL[],int left,int right){
    if(leftlength;
    if(tempL){
        MSort(L,tempL,1,n);
    }
}




//快速排序
//寻找枢轴的正确位置
int partition(SqList *L,int low,int high){
    int i,j,pivot;
    i=low;
    pivot=high;
    for(j=i;jr[j]r[pivot]){
            swap(L,i,j);
            i++;
        }
    }
    swap(L,i,high);
    return i;
}

//递归对枢轴两边的序列进行排序
void QSort(SqList *L,int low,int high){
    if(lowlength);
}


int main(){
    SqList L;
    SqList L1,L2,L3,L4,L5,L6,L7;

    CreatList(&L);
    L1.length=L2.length=L3.length=L4.length=L5.length=L6.length=L7.length=L.length;
    for(int i=1;i<=L.length;i++){
        L1.r[i]=L2.r[i]=L3.r[i]=L4.r[i]=L5.r[i]=L6.r[i]=L7.r[i]=L.r[i];
    }
    

    clock_t start_time1=clock();
    BubbleSort(&L1);
    clock_t end_time1=clock();
    //cout<					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5709972.html

排序算法学习笔记

发表评论

评论列表（0条）