iOS 算法~快速排序实现

作者: 石虎132 | 来源:发表于2017-12-23 10:25 被阅读191次

//联系人:石虎QQ:1224614774 昵称:嗡嘛呢叭咪哄

一、概念:

快速排序: 是高快省的排序算法,在快速排序算法中,使用了分治策略。首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束。

优点:

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。

这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。

空间复杂度:

当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。

代码实现

voidsort(int*a,intleft,intright) {

if(left >= right)return;

inti = left;

intj = right;

intkey = a[left];

while(i < j) {

while(i < j && key >= a[j]) {

j--;

}

a[i] = a[j];

while(i < j && key <= a[i]) {

i++;

}

a[j] = a[i];

}

a[i] = key;

sort(a, left, i-1);

sort(a, i+1, right);

}

二、快速排序的原理图

     快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

图:帮助理解

注意:此图非作者绘制;

谢谢!!!

相关文章

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • 手撕代码 之 快速排序

    1.实现快速排序算法 问题描述给定一个无序数组int[ ] a,使用快速排序算法进行排序。 解题思路对于快速排序,...

  • 三大排序算法

    归并排序[稳定的排序算法] 递归实现 非递归实现 快速排序[不稳定的排序算法] 堆排序[不稳定的排序算法]

  • 快速排序

    手写java版快速排序算法实现

  • 基础算法|快速排序

    快速排序(Quicksort),是对冒泡排序算法的一种改进。 快速排序算法通过多次比较和交换来实现排序,其排序流程...

  • iOS 算法~快速排序实现

    //联系人:石虎QQ:1224614774 昵称:嗡嘛呢叭咪哄 一、概念: 快速排序: 是高快省的排序算法,在快速...

  • 快速排序&快速排序与归并排序的对比

    快速排序算法 快速排序算法是从上到下解决问题使用递归实现,通过巧妙的方式,实现原地排序 分析时间复杂度O(nlog...

  • 数据结构02-高效排序算法

    第二章 高效排序算法 第二章 高效排序算法一、快速排序基本思想快速排序图示一次划分C 语言实现Java 语言实现算...

  • python 排序算法

    文章概述 介绍各大常用经典的排序算法和效率,以及python实现常用算法(冒泡排序,选择排序,快速排序,插入排序)...

网友评论

    本文标题:iOS 算法~快速排序实现

    本文链接:https://www.haomeiwen.com/subject/dubfgxtx.html