常见排序算法原理及代码示例

深藏阁楼爱情的钟 2022-06-04 09:44 233阅读 0赞

### 声明：为简便描述算法，以下排序对象arr\[ \]为整型数组，len为其长度，且按不降序排序。 ###

### 一、插入排序 ###

**1.直接插入排序**

1）原理：将数组分为有序和无序两部分，有序部分一开始只有数组的第一个元素。对于无序部分的每个元素，要插入到有序数列中，方法是与有序部分的末尾元素作比较，若前者大于后者则前者位置不变；否则，往前检索，同时将这个元素往后移动(检索一次，移动一次)，直到找到这个待插入元素小于第n个元素且大于或等于第n-1个元素的位置，然后将其插入到这个位置。以此类推，直到无序数列元素个数为0。

2）C代码实现

void insert_sort(int arr[],int len)
    {
        int i,j,k;
        for(i=1;i<=len;i++){
            j=i-1;
            k=arr[i];
            while(j>-1&&k<arr[j]){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=k;
        }
    }

直接插入排序是稳定的，时间复杂度为O(n^2)。

**2.二分插入排序**

1）原理：与直接插入排序相似，不同的是利用二分查找的方法，对已排序的序列折半地找到要插入的位置，然后将该位置后面的元素后移。

2）C代码实现

void bin_sort(int arr[],int len)
    {
        if(len==2 && arr[0]>arr[1]){
            arr[0]+=arr[1];arr[1]=arr[0]-arr[1];arr[0]-=arr[1];return;
        }
        int i,j;
        for(i=1;i<len;i++){
            int t=arr[i],left=0,right=i-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(t<arr[mid])  right=mid-1;
                else    left=mid+1;
            }
            for(j=i-1;j>=left;j--)  arr[j+1]=arr[j];
            if(left!=i) arr[left]=t;
        }
    }

二分插入排序是稳定的，时间复杂度为O(n^2)。

**3.表插入排序**

1）原理：表插入排序的目的是在直接插入排序的基础上减少移动元素的次数，其排序对象为单链表。跟直接插入排序一样，在已排序序列中，找到待插入元素要插入的位置，进行单链表的插入操作。

2）C代码实现

plist list_sort(plist head)//head指向空头结点
    {
        plist pre,now,p,q;//pre为now的前一个指针
        pre=head->next;
        if(pre==NULL)   return head;
        now=pre->next;
        if(now==NULL)   return head;//空链表或只有一个节点
        while(now){
            q=head;p=head->next;
            while(p!=now&&p->info<=now->info){
                q=p;p=p->next;//查找位置
            }
            if(p==now){//now位置不变
                pre=pre->next;
                now=pre->next;
                continue;
            }
            pre->next=now->next;//使now脱链
            q->next=now;
            now->next=p;
            now=pre->next;
        }
        return head;
    }

表插入排序是稳定的，时间复杂度为O(n^2)。

**4.shell排序**

1）原理：希尔排序是对直接插入排序的改进。先取一个整数d1<n，把arr分为d1组，距离为d1倍数的所有元素看成一组，先在各组内进行直接插入排序（或其它排序法），然后取d2<d1重复同样的分组和排序，直到di=1，即对arr全部元素进行排序。shell排序一趟排序就可以消去多个逆序对，效率上优于直接插入排序。 d 的选取方法不一，至今也不能确定哪一最好，这里姑且取当前d为前一个d的一半。

2）C代码实现

void shell_sort(int arr[],int len)
    {
        int i,j,k,t;
        for(k=len/2;k>0;k/=2){//k为当前d
            for(i=k;i<len;i++){
                t=arr[i];
                for(j=i-k;j>=0&&t<arr[j];j-=k)//各组中大的元素往后移
                    arr[j+k]=arr[j];
                arr[j+k]=t;
            }
        }
    }

shell排序是不稳定的，时间复杂度比较复杂，这里不给出。

### 二、选择排序 ###

**1.直接选择排序**

1）原理：先在数组中找出最小值，通过交换将其放在数组第一位，然后再从剩余的未排序数组中找到最小值，将其放在已排序数组的末尾。以此类推，直到整个数组排好序。

2）C代码实现

void select_sort(int arr[],int len)
    {
        int i,j,t,k;
        for(i=0;i<len-1;i++){
            k=i;
            for(j=i+1;j<len;j++){
                if(arr[k]<arr[j])//找最小值
                    k=j;
            }
            if(i!=k){
                t=arr[i];arr[i]=arr[k];arr[k]=t;
            }
        }
    }

直接选择排序是不稳定的，时间复杂度为O(n^2)。

**2.堆排序**

1）原理：先把数组元素构造成大根堆，然后从堆中不断选出最大元素，从而达到排序的目的。排序结果需要保存，为了节省空间，可以利用原始数组。

如何构造大根堆？为产生初始堆，只要从含有内部结点的最小子树（这种树的根在由下向上数的第二层）开始，调用sift函数，调整各个子树使得都满足堆序性。对这一层的调整结束后，再对上一层的子树做同样操作。这样，由下向上地调用sift函数调整树中各层子树，当达到根结点时，整棵树成为一个堆。

如何不断选出堆中的最大元素？只需将堆顶的最大元素（数组首元素）与最后一个元素交换，同时使堆的大小减一。这种交换可能破坏堆序性，所以每次交换，都要调用创建堆时所使用的函数sift，从后向前逐步把待排序元素调整为最大堆，直到堆中只剩下一个元素，此时数组元素已排好序。

2）C代码实现

void sift(int arr[],int heapSize,int i)
    {
        int tmp=arr[i],child=2*i+1;
        while(child<heapSize){
            if(child<heapSize-1 && arr[child]<arr[child+1])//选择比较大的子节点
                child++;
            if(arr[child]>tmp){
                arr[i]=arr[child];//将大节点上移
                i=child;
                child=i*2+1;
            }
            else    break;//调整结束
        }
        arr[i]=tmp;
    }
    
    void heap_sort(int arr[],int len)
    {
        int i;
        for(i=len/2-1;i>=0;i--) sift(arr,len,i);//初始创建堆
        for(i=len-1;i>0;i--){//len-1趟堆排序
            arr[i]+=arr[0];
            arr[0]=arr[i]-arr[0];
            arr[i]-=arr[0];
            sift(arr,i,0);//调整堆，注意i起控制调整范围的作用
        }
    }

堆排序与下面的快速排序相比效率差不多，但堆排序的优点是，数据的初始化分布情况对它的工作效率没有大的影响。堆排序是不稳定的，时间复杂度为O(n*log2*n)。

### 三、交换排序 ###

**1.冒泡排序**

1）原理：首先比较arr\[0\]和arr\[1\]，若前者大，则交换位置，否则不交换；然后比较新的arr\[1\]和arr\[2\]作同样处理，以此类推，直到处理完第n-1和第n个元素为止，这称为一趟冒泡。经过这次冒泡，arr中的最大元素被交换到第n个位置上。此后，再对前n-1个元素进行同样处理，使得它们中的最大者又被交换到第n-1个位置上。以此类推，最多经过n-1趟冒泡就能完成排序。可以设置一个标志 noswap 表示本次冒泡是否有元素交换，如果没有说明整个arr已排好序。

除了上述的方式一之外，还可以变形成另一种，方式一是相邻元素进行比较，方式二可以将一个位置上的元素与其它元素进行比较，比如第一趟交换，arr\[0\]与arr\[n\]（0<n<len）进行比较，如果arr\[0\] > arr\[n\] 则交换，这一趟交换后，保证了arr\[0\]存放的就是最小值。第二趟排序比较arr\[1\]和arr\[n\]并交换（1<n<len）保证次最小值就是arr\[1\],以此类推进行len-1次比较，最终保证整个arr排好序。我这种方法为最小值沉淀法，不过这种方式缺点是不能设置noswap标志位，因为比较的两个元素不是相邻，不能保证一次交换里面其它元素之间的大小关系。最小沉淀法是从arr头部比较，其实也可以从arr尾部比较，每次交换将最大值放在arr最后一个位置，和最小沉淀法的思想一样，我称之为最大值冒泡。

2）方式一（C代码实现）

void bubble_sort(int arr[],int len)//从数组头部开始，各元素与其后面的每个元素作比较
    {
        int i,j,t;
        for(i=0;i<len-1;i++){
            int noswap=0;
            for(j=i;j<len-1-i;j++)
            if(arr[j+1]<arr[j]){
                t=arr[j];arr[j]=arr[j+1];arr[j+1]=t;
                noswap=1;
            }
            if(!noswap)  break;
        }
    }

2）方式二（Java实现）

//        最小值沉淀
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        arr[i] += arr[j];
                        arr[j] = arr[i] - arr[j];
                        arr[i] -= arr[j];
                    }
                }
            }
    
    //        最大值冒泡
            for (int i = arr.length - 1; i > 0; i--) {
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[i] < arr[j]) {
                        arr[i] += arr[j];
                        arr[j] = arr[i] - arr[j];
                        arr[i] -= arr[j];
                        System.out.println(i);
                    }
                }
            }

冒泡排序是稳定的，时间复杂度为O(n^2)。

**2.快速排序**

1）原理：在待排序的数组中取一个元素作为准基数（取数组头、中、尾三个元素的中位数，以减少比较和移动次数），把所有比它小的元素移到左边，把所有比它大的元素移到右边，中间放准基数，称为一趟排序。然后，对前后两个子序列进行同样处理，直到整个数组排好序。具体算法步骤可参见http://developer.51cto.com/art/201403/430986.htm

2）C代码实现

void quick_sort(int arr[],int left,int right)
    {
        int i=left,j=right,k=arr[left],t;//k储存准基数，假设arr[left]在arr[(left+right)/2]和arr[right]的中间,而且开始排序时left=0，否则可交换得到。
        if(i>j)
            return ;
        while(i!=j){
            while(i<j&&arr[j]>=k)//必须是先从右边比较，否则准基数归位时将出错
                j--;
            while(i<j&&arr[i]<=k)
                i++;
            if(i<j){
                t=arr[i];arr[i]=arr[j];arr[j]=t;
            }
        }
        arr[left]=arr[i];
        arr[i]=k;
        quick_sort(arr,left,i-1);
        quick_sort(arr,i+1,right);
    }

快速排序是不稳定的，时间复杂度为O( n*log2*n )。

### 四、归并排序 ###

1）原理：归并排序采用递归实现，总体上有两个步骤（分解与归并）：  
先将待排序数组R\[0...n-1\]分解成n个长度为1的有序序列（其实是一个元素），将相邻的两个元素有序归并，得到n/2个长度为2的有序序列；然后将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。  
归并的具体步骤：比较arr\[i\]和arr\[j\],将较小值复制到新的数组new\_arr\[k\],同时让i，j都加上1。如此循环下去，直到其中一个数组被复制完，再让另一个数组所剩余的元素（已排序）直接拼接到的new\_arr的后面。

2）C代码实现

void merg(int arr[],int new_arr[],int left,int right,int mid)
    {
        int i=left,j=mid+1,k=i;
    
        while(i!=mid+1&&j!=right+1)
        {
            if(arr[i]>arr[j])
                new_arr[k++]=arr[j++];
            else
                new_arr[k++]=arr[i++];
        }
        while(i!=mid+1)
            new_arr[k++]=arr[i++];
        while(j!=right+1)
            new_arr[k++]=arr[j++];
        for(i=left;i<=right;i++)
            arr[i]=new_arr[i];
    }
    
    void merge_sort(int arr[],int new_arr[],int left,int right)
    {
        int mid;
        if(left<right)
        {
            mid=(left+right)/2;
            merge_sort(arr,new_arr,left,mid);//左分解
            merge_sort(arr,new_arr,mid+1,right);//右分解
            merg(arr,new_arr,left,right,mid);//调用 merg子函数 归并
        }
    }

归并排序是稳定的，时间复杂度为O( n*log2*n )。