当前位置：文档之家 › 排序算法

排序算法

  • 格式：doc
  • 大小：52.00 KB
  • 文档页数：17

第 1 页 共 17 页 排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

分类

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个关键字有序的序列。

稳定度(稳定性)

一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4,1)(3,1)(3,7)(5,6)在这个状况下，有可能产生两种不同 第 2 页 共 17 页 的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有:

(3,1)(3,7)(4,1)(5,6) (维持次序)

(3,7)(3,1)(4,1)(5,6) (次序被改变)

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

在计算机科学所使用的排序算法通常被分类为:

(a)计算的复杂度(最差、平均、和最好性能)，依据列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且坏的性能是

O(n^2)。对于一个排序理想的性能是 O(n)。

而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。

(b)存储器使用量(空间复杂度)(以及其他电脑资源的使用)

(c)稳定度:稳定的排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。

(d)一般的方法:插入、交换、选择、合并等等。交换排 第 3 页 共 17 页 序包含冒泡排序和快速排序。插入排序包含希尔排序，选择排序包括堆排序等。

C++算法

C++自带的algorithm库函数中提供了排序算法。

自带排序算法的一般形式为:

sort(arr+m,arr+n);//将数组arr的下标为m的元素到下标为n-1的元素进行从小到大排序

sort(arr+m,arr+n,comp);//与sort(arr+m,arr+n)相比，这个写法可以自己定义排序的规则，其中，comp为自定义的函数

对于sort(arr+m,arr+n)我们举个简单的例子，这个程序实现从键盘读入10个数，然后从小到大输出的功能:

当然，有时我们需要从大到小的进行排序。那么我们可以用sort(arr+m,arr+n,comp)进行排序。

不过，在调用sort(arr+m,arr+n,comp)之前我们需要自己写个comp函数。

从大到小排序的comp函数可以这样写:

下面是10个数从大到小排序的代码:

在更多情况下，我们不仅对一个特征进行排序，而是多个特征。例如将学生的成绩进行排序，当然用上面的做法是行不通的。这是，我们就想到了结构体这种数据类型。当我们采用sort()函数的默认规则排序结构体时，sort()默认结构 第 4 页 共 17 页 体中的第一个成员为第一关键字，第二个成员为第二关键字，……，第N个元素为第N关键字，然后从小到大排序。

例如我们要将学生的成绩从大到小排序，当成绩相同时，根据姓名字典序小的优先规则进行排序。显然我们无法采用默认规则进行排序。

这时我们可以定义这样的comp:

算法列表

在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。

稳定的

冒泡排序(bubble sort) - O(n^2)

鸡尾酒排序(Cocktail sort，双向的冒泡排序) - O(n^2)

插入排序(insertion sort)- O(n^2)

桶排序(bucket sort)- O(n); 需要 O(k) 额外空间

计数排序(counting sort) - O(n+k); 需要 O(n+k) 额外空间

合并排序(merge sort)- O(nlog n); 需要 O(n) 额外空间

原地合并排序- O(n^2)

二叉排序树排序 (Binary tree sort) - O(nlog n)期望时间; O(n^2)最坏时间; 需要 O(n) 额外空间

鸽巢排序(Pigeonhole sort) - O(n+k); 需要 O(k) 额 第 5 页 共 17 页 外空间

基数排序(radix sort)- O(n·k); 需要 O(n) 额外空间

Gnome 排序- O(n^2)

图书馆排序- O(nlog n) with high probability，需要

(1+ε)n额外空间

不稳定的

选择排序(selection sort)- O(n^2)

希尔排序(shell sort)- O(nlog n) 如果使用最佳的现在版本

组合排序- O(nlog n)

堆排序(heapsort)- O(nlog n)

平滑排序- O(nlog n)

快速排序(quicksort)- O(nlog n) 期望时间，O(n^2)

最坏情况; 对于大的、乱数列表一般相信是最快的已知排序

Introsort- O(nlog n)

耐心排序- O(nlog n+ k) 最坏情况时间，需要 额外的

O(n+ k) 空间，也需要找到最长的递增子串行(longest

increasing subsequence)

不实用的

Bogo排序- O(n× n!) 期望时间，无穷的最坏情况。

Stupid sort- O(n^3); 递归版本需要 O(n^2) 额外存储器 第 6 页 共 17 页 珠排序(Bead sort) - O(n) or O(√n)，但需要特别的硬件

Pancake sorting- O(n)，但需要特别的硬件

stooge sort--O(n^2.7)很漂亮但是很耗时

排序算法

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序

冒泡排序

选择排序

快速排序

堆排序

归并排序

基数排序

希尔排序

插入排序

插入排序是这样实现的:

1、首先新建一个空列表，用于保存已排序的有序数列(我 第 7 页 共 17 页 们称之为"有序列表")。

2、从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。

3、重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i

对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x "腾位置"，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。

冒泡排序

冒泡排序是这样实现的:

1、从列表的第一个数字到倒数第二个数字，逐个检查:若某一位上的数字大于他的下一位，则将它与它的下一位交换。

2、重复1号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但冒泡排序是原地排序的，也就是说它不需要额外的存储空间。 第 8 页 共 17 页 选择排序

选择排序是这样实现的:

1、设数组内存放了n个待排数字，数组下标从1开始，到n结束。

2、初始化i=1

3、从数组的第i个元素开始到第n个元素，寻找最小的元素。

4、将上一步找到的最小元素和第i位元素交换。

5、i++,直到i=n-1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n^2)的。

举例:

564

比如说这个，我想让它从小到大排序，怎么做呢?

第一步:从第一位开始找最小的元素，564中4最小，与第一位交换。结果为465

第二步:从第二位开始找最小的元素，465中5最小，与第二位交换。结果为456

第三步:i=2，n=3，此时i=n-1，算法结束

完成

快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思 第 9 页 共 17 页 想:先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

时间复杂度

平均时间复杂度

插入排序 O(n^2)

冒泡排序 O(n^2)

选择排序 O(n^2)

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

基数排序 O(n)

希尔排序 O(n^1.25)

复杂度

简单排序算法

由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境

下运行通过。因为没有涉及MFC和WINDOWS的内

合集下载

十大经典排序算法总结

十大经典排序算法总结

⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {

if (array.length == 0)

return array;

for (int i = 0; i < array.length; i++)

for (int j = 0; j < array.length - 1 - i; j++)

if (array[j + 1] < array[j]) {

int temp = array[j + 1];

array[j + 1] = array[j];

简单排序算法

简单排序算法

简单排序算法

排序算法是计算机科学中最基本、最常用的算法之一。通过对原始数据集合进行排序，可以更方便地进行搜索、统计、查找等操作。常用的排序算法有冒泡排序、选择排序、插入排序等。本文将介绍这些简单排序算法的具体实现及其优缺点。

一、冒泡排序（BubbleSort）

冒泡排序是一种基础的交换排序算法。它通过不断地交换相邻的元素，从而将数据集合逐渐排序。具体实现步骤如下：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2.对每一对相邻元素做同样的工作，从第一对到最后一对，这样一轮排序后，就可以确保最后一个元素是最大的元素；

3.针对所有元素重复以上的步骤，除了最后一个；

4.重复步骤1~3，直到排序完成。

冒泡排序的优点是实现简单、容易理解。缺点是排序效率较低，尤其是对于较大的数据集合，时间复杂度为O(n²)。

二、选择排序（SelectionSort）

选择排序是一种基础的选择排序算法。它通过在数据集合中选择最小的元素，并将其放置到最前面的位置，然后再从剩余元素中选出最小的元素，放置到已排序部分的末尾。具体实现步骤如下：1.在未排序序列中找到最小元素，存放到排序序列的起始位置；

2.再从剩余未排序元素中继续寻找最小元素，放到排序序列末尾；

3.重复步骤1~2，直到排序完成。

选择排序的优点是实现简单、固定时间复杂度O(n²)。缺点是排序效率仍然较低，尤其是对于大数据集合，因为每次只能交换一个元素，所以相对于冒泡排序，它的移动次数固定。

三、插入排序（InsertionSort）

插入排序是一种基础的插入排序算法。它将未排序的元素一个一个插入到已排序部分的正确位置。具体实现步骤如下：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后往前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；

5.将新元素插入到该位置后；

【转】三种快速排序算法以及快速排序的优化

【转】三种快速排序算法以及快速排序的优化

【转】三种快速排序算法以及快速排序的优化

⼀. 快速排序的基本思想

快速排序使⽤分治的思想，通过⼀趟排序将待排序列分割成两部分，其中⼀部分记录的关键字均⽐另⼀部分记录的关键字⼩。之后分别对这

两部分记录继续进⾏排序，以达到整个序列有序的⽬的。

⼆. 快速排序的三个步骤

1) 选择基准：在待排序列中，按照某种⽅式挑出⼀个元素，作为 “基准”（pivot）；

2) 分割操作：以该基准在序列中的实际位置，把序列分成两个⼦序列。此时，在基准左边的元素都⽐该基准⼩，在基准右边的元素都⽐基准

⼤；

3) 递归地对两个序列进⾏快速排序，直到序列为空或者只有⼀个元素；

三. 选择基准元的⽅式

对于分治算法，当每次划分时，算法若都能分成两个等长的⼦序列时，那么分治算法效率会达到最⼤。也就是说，基准的选择是很重要的。

选择基准的⽅式决定了两个分割后两个⼦序列的长度，进⽽对整个算法的效率产⽣决定性影响。

最理想的⽅法是，选择的基准恰好能把待排序序列分成两个等长的⼦序列。

⽅法⼀：固定基准元（基本的快速排序）

思想：取序列的第⼀个或最后⼀个元素作为基准元。

///

/// 1.0 固定基准元（基本的快速排序）

///

public static void QsortCommon(int[] arr, int low, int high)

{

if (low >= high) return; //递归出⼝

int partition = Partition(arr, low, high); //将 >= x 的元素交换到右边区域，将 <= x 的元素交换到左边区域

QsortCommon(arr, low, partition - 1);

QsortCommon(arr, partition + 1, high);

}

///

/// 固定基准元，默认数组第⼀个数为基准元，左右分组，返回基准元的下标

///

public static int Partition(int[] arr, int low, int high)

十大排序算法

十大排序算法

⼗⼤排序算法

算法之排序

排序算法基本上是我们⽆论是在项⽬中还是在⾯试中都会遇到的问题，加上最近在看《算法》这本书，所以就准备好好的将排序算法整理⼀下。

所有排序算法都是基于 Java 实现，为了简单，只使⽤了int类型，从⼩到⼤排序基本排序⾼效的排序各⼤排序的时间测试

如何选择排序

排序之基本排序算法

准备阶段：有⼀个交换位置的函数exc

/**

* 交换a数组中i和j的位置

* @param a 需要交换的数组

* @param i 位置

* @param j 位置

*/

public static void exc(int a[],int i,int j){

// 当他们相等的时候就没必要进⾏交换

if(a[i] != a[j]){

a[i] ^= a[j];

a[j] ^= a[i];

a[i] ^= a[j];

}

}

基本排序算法主要是分为插⼊排序，选择排序，冒泡排序和梳排序。

选择排序

原理： 选择排序的原理很简单，就是从需要排序的数据中选择最⼩的（从⼩到⼤排序），然后放在第⼀个，选择第⼆⼩的放在第⼆个……

代码：

/**

* 选择排序

* @param a 进⾏排序的数组

*/

public static int[] selectionSort(int a[]){

int min;

for(int i=0;i

min = i;

// 这个for循环是为了找出最⼩的值

for (int j = i+1; j < a.length; j++) {

if(a[min]>a[j]){

min = j;

}

}

/** 如果第⼀个取出的元素不是最⼩值，就进⾏交换

* 意思就是：如果取出的元素就是最⼩值，那么就没有必要进⾏交换了 */

if(min != i){

// 进⾏交换

exc(a, i, min);

}

}

return a;

}

选择排序的动画演⽰

img

假如数组的长度是N，则时间复杂度：

进⾏⽐较的次数：(N-1)+(N-2)+……+1 = N(N-1)/2进⾏交换的次数：N