交换排序

交换排序:根据序列中俩个元素关键字的比较结果来对换这两个记录在序列中的位置。

1.冒泡排序

定义:从后往前(或从前往后)俩俩比较相邻元素的值,若为逆序(即arr[i-1] > arr[i]),则交换它们,直到序列比较完成。称这样的过程为“一趟”冒泡排序。
代码实现:

  /**
    冒泡排序
    空间复杂度:O(1)
    最好情况(有序):O(n)
    最坏情况(逆序):O(n^2)
    平均时间复杂度:O(n^2)
    稳定性:稳定
    对链表进行排序:是
*/
void MyBubbleSort(int arr[], int n){
    int temp;   // 定义暂存变量
    int flag;   // 如果一趟没有发生交换则直接退出循环
    for(int i=0; i<n-1; i++){
        flag = 0;
        for(int j=n-1;j>i;j--){
            if(arr[j-1] > arr[j]){
                temp = arr[j-1];    // 交换俩者
                arr[j-1] = arr[j];
                arr[j] = temp;
                flag = 1;
            }
        }
        if(flag == 0){
            return;
        }
    }
}

2.快速排序

算法思想:在待排序表L[1...n]中任取一个元素作为枢轴(或基准,通常取首元素),通过一趟排序将待排序表划分为独立的俩部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中所有元素小于基准,L[k+1...n]中所有元素大于等于基准,则基准元素放在了其最终位置L(k)上,这个过程称为一次“划分”。然后分别递归的对俩个子表重复上述过程,直至没部分内只有一个元素或空为止,即所有元素放在了其最终位置上。
每一层的递归调用只需要处理剩余的待排序元素,时间复杂度不超过O(n)

  • 1.时间复杂度=O(n*递归层数)
    最好时间复杂度=O(n(lnn/ln2))
    最坏时间复杂度=O(n^2)
    平均时间复杂度=O(n(lnn/ln2))
    快速排序是所有内部排序算法中平均性能最优的排序算法
  • 2.空间复杂度=O(递归层数)——主要是递归工作栈
    最好空间复杂度=O((lnn/ln2))
    最坏空间复杂度=O(n)
  • 3.若初始序列有序或逆序,则快速排序的性能最差(因为每次选择的都是最靠边的元素)
  • 4.尽量选择可以把数据中风的基准元素
    A:选头,中,尾三个位置的元素,取中间值作为枢轴元素;
    B:随机选择一个元素作为基准
  • 5.稳定性:不稳定

代码实现:

 // 快速排序
void QuickSort(int arr[], int low, int high){
    if(low < high){
        int pivotPosition = SeparateParts(arr, low, high);  // 划分
        QuickSort(arr, low, pivotPosition-1);   // 划分左子表
        QuickSort(arr, pivotPosition+1, high);  // 划分右子表
    }
}

// 用第一个元素将待排序列划分成左右俩个部分
int SeparateParts(int arr[], int low, int high){
    int pivot = arr[low]; // 数组的第一个元素作为基准
    while(low < high){
        while(low<high && arr[high]>=pivot)
            --high;
        arr[low] = arr[high];   // 比基准小的元素移动到左端
        while(low<high && arr[low]<=pivot)
            ++low;
        arr[high] = arr[low];   // 比基准大的元素移动到右端
    }
    arr[low] = pivot;   // 基准元素存放到最终位置
    return low; // 返回存放基准的最终位置
}

3.总结

通过对俩种交换排序的算法学习,使自己的思维得到了显著的提升,继续加油继续进步。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,874评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,102评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,676评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,911评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,937评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,935评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,860评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,660评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,113评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,363评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,506评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,238评论 5 341
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,861评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,486评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,674评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,513评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,426评论 2 352

推荐阅读更多精彩内容