必会的排序算法

一、基本的排序算法

1、冒泡排序

基本思想：

n个数一共要进行n-1趟排序，每一趟排序都是两两比较，小的数一路交换着往前走，大的数就自然往后靠，每一趟排序都会确定一个数的最终位置。

#冒泡排序python实现
def BubbleSort():
    arr = [9,5,12,8,3,11]
    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            if arr[j]<arr[i]:
                arr[i],arr[j] = arr[j],arr[i]
    return arr

//冒泡排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void BubbleSort(){
    int arr[6] = {9,5,12,8,3,11};
    int length = sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<length-1;i++){
        for(int j=i+1;j<length;j++){
            if(arr[j]<arr[i]){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

2、选择排序

基本思想：

从下标0开始遍历整个数组，找到最小的数与下标为0的数交换位置，然后从下标1开始遍历数组，找到最小的与下标为1的数交换位置......直到遍历完整个数组。

#选择排序python实现
def SelectSort():
    arr = [9,5,12,8,3,11]
    for i in range(len(arr)):
        indexOfmin = i
        for j in range(i+1,len(arr)):
            if arr[j]<arr[i]:
                indexOfmin = j
        if indexOfmin!=i:
            arr[i],arr[indexOfmin] = arr[indexOfmin],arr[i]
    return arr

//选择排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void SelectSort(){
    int arr[6] = {9,5,12,8,3,11};
    int length = sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<length;i++){
        int indexOfmin_number = i;
        for(int j=i+1;j<length;j++){
            if(arr[j]<arr[i]){
                indexOfmin_number=j;
            }
        }
        if(indexOfmin_number!=i){
            int temp = arr[indexOfmin_number];
            arr[indexOfmin_number] = arr[i];
            arr[i] = temp;
        }
    }
}

3、插入排序

基本思想：

对于一个待排序的数组，把下标为0的第一个数字看作是“排好序”的数组，然后从下标为1的第二个数开始，依次与“排好序”的数字比较，并适当移动“排好序”的数字并把该数字插到合适的位置，直到整个数组遍历完毕。

#插入排序python实现
def InsertSort():
    arr = [9,5,12,8,3,11]
    for i in range(len(arr)-1):
        for j in range(i+1,0,-1):
            if arr[j]<arr[j-1]:
                arr[j],arr[j-1] = arr[j-1],arr[j]
            else:
                break
    return arr

//插入排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void InsertSort(){
    int arr[6] = {9,5,12,8,3,11};
    int length = sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<length-1;i++){
        for(int j=i+1;j>0;j--){
            if(arr[j]<arr[j-1]){
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

4、快速排序

基本思想：

使用分治法（Divide and conquer）策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。
1、挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2、分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3、递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

看这个图我觉得能很好的帮助你理解原理。 
#快速排序python实现
def Partition(arr, left, right):#切分：找基准点
    i,j = left,right
    # i < j 意味着还没有找到基准点
    while (i < j):
        # 从右边开始，保证i < j并且arr[i]小于或者等于arr[j]，即左边的数小于等于右边的数
        while (i < j and arr[i] <= arr[j]):
            j-=1
        # 跳出循环，两种可能：j >= i 或者arr[i]大于arr[j]。如果是前者，就直接跳出大循环了，返回基准点；如果是后者，那就意味着右边的数小于左边的数了，所以需要将两个数交换位置。
        if (i < j):
            arr[i],arr[j] = arr[j],arr[i]
        #右边的数小于左边的数，交换位置之后就要从左边往右边开始遍历、比较、交换。
        while (i < j and arr[i] <= arr[j]):
            i+=1
        if (i < j):
            arr[i],arr[j] = arr[j],arr[i]
    # i>=j 说明基准点已经找到了
    return i

def QuickSort(arr,left,right):#递归调用：对由基准点分开的小数组进行排序
     if (left<right):
        pivot = Partition(arr,left,right)
        #沿着基准点切开数组，然后对左右两边进行递归
        QuickSort(arr,left,pivot-1)
        QuickSort(arr,pivot+1,right)
     return arr
print(QuickSort([9,5,12,8,3,11],0,5))

//快速排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
int Partition(int arr[],int left,int right){
    while(left<right){
        while(left<right && arr[left]<arr[right]){
            right -= 1;
        }
        if(arr[left]>=arr[right]){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        while(left<right && arr[left]<arr[right]){
            left += 1;
        }
        if(arr[left]>=arr[right]){
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    return left;
}
int QuickSort(int arr[],int left,int right){
    if(left<right){
        int pivot = Partition(arr,left,right);
        QuickSort(arr,left,pivot-1);
        QuickSort(arr,pivot+1,right);
    }
    return 0;
}

5、希尔排序

基本思想：

希尔排序又称为“缩小增量排序”。对于有n个待排序元素的序列，首先取一个整数step(step<n)作为间隔，将全部元素分为step个子序列(也就是把所有相隔距离为step的元素放在同一个子序列中)，然后在每个子序列中分别采用直接插入排序算法进行排序。所有子序列排序完毕之后得到新的待排序序列，然后缩小间隔step(比如说：ste/=2),重复上述过程直到step等于1。

#希尔排序python实现
def ShellSort(arr):
    step = len(arr)//2
    while step>=1:
        for i in range(step,len(arr)):
            for j in range(i,step-1,-step):
                if arr[j]<arr[j-step]:
                    arr[j],arr[j-step] = arr[j-step],arr[j]
                else:
                    break
        step //= 2
    return arr

//希尔排序c++实现
#include <iostream>
#include "stdio.h"
using namespace std;
void ShellSort(int arr[],int length){
    int step = 1;
    while(step < length/3){
        step = step*3 + 1;
    }
    while(step>=1){
        for (int i = 0; i < step; i++) {
            int j = i+step;
            while(j<length){
                if(arr[j]<arr[j-step]){
                    int temp = arr[j];//先保存下标为j的值
                    int k = j-step;
                    while(k>=0&&temp<arr[k]){  //从j-step开始比较，把大于arr[j]的数往后挪，前面腾出位置存放arr[j]
                        arr[k+step] = arr[k];
                        k -= step;
                    }
                    arr[k+step] = temp;//arr[j]存放到最终合适的位置
                }
                j += step;
            }
        }
        step /= 3;
    }
}

6、堆排序

基本思想：

堆排序是利用堆这个数据结构而设计的一种排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

  1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
    主要步骤为：1、建堆；2、交换调整。
#堆排序python实现
def BuildHeap(arr,start,length):
    while 2*start+1 <= length :
        j = 2*start+1
        if j<length and arr[j+1]>arr[j]:
            j+=1
        if arr[j] < arr[start]:
            break
        arr[start],arr[j] = arr[j],arr[start] #把大的数移到上面去
        start = j
def HeapSort(arr):
    length = len(arr)
    for i in range(length//2,-1,-1):  #构建一个堆
        BuildHeap(arr,i,length-1)
    length -= 1
    while(length>0):    #排序
        arr[0],arr[length] = arr[length],arr[0]
        length -= 1
        BuildHeap(arr,0,length)
    return arr

//堆排序c++实现
#include <iostream>
#include <vector>
using namespace std;
//辅助交换函数
void Swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
//堆排序的核心是建堆,传入参数为数组，根节点位置，数组长度
void Heap_build(int a[], int root, int length){
    int lchild = root * 2 + 1;//根节点的左子结点下标
    if (lchild < length){    //左子结点下标不能超出数组的长度
        int flag = lchild;//flag保存左右节点中最大值的下标
        int rchild = lchild + 1;//根节点的右子结点下标
        if (rchild < length){      //右子结点下标不能超出数组的长度(如果有的话)
            if (a[rchild] > a[flag]){      //找出左右子结点中的最大值
                flag = rchild;
            }
        }
        if (a[root] < a[flag]){
            //交换父结点和比父结点大的最大子节点
            Swap(a[root], a[flag]);
            //从此次最大子节点的那个位置开始递归建堆
            Heap_build(a, flag, length);
        }
    }
}
void Heap_sort(int a[], int len){
    for (int i = len / 2-1; i >= 0; --i) {   //从最后一个非叶子节点的父结点开始建堆
        Heap_build(a, i, len);
    }
    for (int j = len - 1; j > 0; --j){    //j表示数组此时的长度，因为len长度已经建过了，从len-1开始
        Swap(a[0], a[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
        Heap_build(a, 0, j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
    }
}

7、归并排序

基本思想：

归并排序的核心思想是“分治”。主要就是两个步骤：
分割：递归地把当前序列平均分割成两半。

合并：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
#归并排序python实现
def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 将大数组分解成一个个只有一个元素的数组
    num = len(alist) // 2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 返回合并后的结果
    return merge(left, right)

def merge(left, right):
    '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
    # l与r为两个有序数组left[]和right[]的下标索引
    l, r = 0, 0
    result = []
    #两个有序数组left[]和right[]都没有合并完就一直比较下去
    while l < len(left) and r < len(right): 
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    #跳出while循环，把两个有序数组left[]和right[]剩下的元素直接加到大数组后面
    result += left[l:]
    result += right[r:]
    return result

print(merge_sort([9,5,12,8,3,11]))

//归并排序c++实现
#include<iostream>
#include<stdio.h>
using namespace std;
void mergearray(int a[],int first,int mid,int last,int result[]){
    int i=first,j=mid+1;
    int n=mid,m=last;
    int k=0;
    while(i<=n&&j<=m){
        if(a[i]<=a[j])
            result[k++]=a[i++];
        else
            result[k++]=a[j++];
    }
    while(i<=n){
        result[k++]=a[i++];
    }
    while(j<=m){
        result[k++]=a[j++];
    }
    for(i=0;i<k;i++){
        a[first+i]=result[i];
    }
}
void mergesort(int a[],int first,int last,int result[]){
    if(first<last){
        int mid=(first+last)/2;
        mergesort(a,first,mid,result);
        mergesort(a,mid+1,last,result);
        mergearray(a,first,mid,last,result);
    }
}
int MergeSort(int a[],int len){
    int *temp=new int [len];
    if(temp==NULL)
        return 0;
    else
        mergesort(a,0,len-1,temp);
    return 1;
}
int main(){
    int arr[] = {9,5,12,8,3,11};
    int n = sizeof(arr)/sizeof(arr[0]);
    MergeSort(arr,n);
    for(int i=0;i<n;i++)
    {
        printf("%d ",arr[i]);
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,384评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,845评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,148评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,640评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,731评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,712评论 1赞 294
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,703评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,473评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,915评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,227评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,384评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,063评论 5赞 340
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,706评论 3赞 324
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,302评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,531评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,321评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,248评论 2赞 352