经典、常用排序算法的原理及 实现以及算法分析

本文介绍了7种最经典、最常用的排序算法，分别是：冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序。对应的时间复杂度如下所示：

整篇文章的主要知识提纲如图所示：

1. 排序算法分析

学习排序算法除了学习它的算法原理、代码实现之外，最重要的是学会如何评价、分析一个排序算法。分析一个排序算法通常从以下几点出发。

1.1. 执行效率

而对执行效率的分析，一般从这几个方面来衡量：

?最好情况、最坏情况、平均情况

除了需要给出这三种情况下的时间复杂度还要给出对应的要排序的原始数据是怎么样的。

?时间复杂度的系数、常数、低阶

大O时间复杂度反应的是算法时间随n的一个增长趋势，比如O(n^2)表示算法时间随n的增加，呈现的是平方的增长趋势。这种情况下往往会忽略掉系数、常数、低阶等。但是实际开发过程中，排序的数据往往是10个、100个、1000个这样规模很小的数据，所以在比较同阶复杂度的排序算法时，这些系

数、常数、低阶不能省略。

?比较次数和交换（或移动）次数

在基于比较的算法中，会涉及到元素比较和元素交换等操作。所以分析的时候，还需要对比较次数和交换次数进行分析。

1.2. 内存消耗

内存消耗其实就是空间复杂度。针对排序算法来说，如果该排序算法的空间复杂度为O(1)，那么这个排序算法又称为原地排序。

1.3. 稳定性是什么

稳定性是指待排序的序列中存在值相等的元素。

在排序之后，相等元素的前后顺序跟排序之前的是一样的。

为什么

我们将排序的原理和实现排序时用的大部分都是整数，但是实际开发过程中要排序的往往是一组对

象，而我们只是按照对象中的某个k e y来进行排序。

比如一个对象有两个属性，下单时间和订单金额。在存入到数据库的时候，这些对象已经按照时间先后的顺序存入了。但是我们现在要以订单金额为主k e y，在订单金额相同的时候，以下单时间为k e y。那么在采用稳定的算法之后，只需要按照订单金额进行一次排序即可。比如有这么三个数据，第一个数据是下单时间、第二数据是订单金额：（20200515、

20）、（20200516、10）、（20200517、30）、

（20200518、20）。在采用稳定的算法之后，排序的

情况如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以发现在订

单金额相同的情况下是按订单时间进行排序的。

2. 经典的常用排序算法

2.1. 冒泡排序

冒泡排序就是依次对两个相邻的元素进行比较，

然后在不满足大小条件的情况下进行元素交换。一趟

冒泡排序下来至少会让一个元素排好序（元素排序好

的区域相当于有序区，因此冒泡排序中相当于待排序

数组分成了两个已排序区间和未排序区间）。因此为

了将n个元素排好序，需要n-1趟冒泡排序（第n 趟的时候就不需要）。

下面用冒泡排序对这么一组数据4、5、6、3、2、1，从小到大进行排序。第一次排序情况如下：

可以看出，经过一次冒泡操作之后，6这个元素已经存储在正确的位置上了，要想完成有所有数据的排

序，我们其实只需要5次这样的冒泡排序就行了。图中给出的是带第6次了的，但是第6次其实没必要。

2.1.1. 优化

使用冒泡排序的过程中，如果有一趟冒泡过程中元素之间没有发生交换，那么就说明已经排序好了，可以直接退出不再继续执行后续的冒泡操作了。

2.1.2. 实现

下面的冒泡排序实现是优化之后的：

/**

* 冒泡排序：

* 以升序为例，就是比较相邻两个数，如果逆序就交换，类似于冒泡；

* 一次冒泡确定一个数的位置，因为要确定 n-1 个数，因此需要 n-1

* 次冒泡；

* 冒泡排序时，其实相当于把整个待排序序列分为未排序区和已排序区

*/

public void bubbleSort(int[] arr, int len) {

// len-1 趟

for (int j = 0; j < len-1; j++) {

int sortedFlag = 0;

// 一趟冒泡

for (int i = 0; i < len-1-j; i++) {

if (arr[i] > arr[i+1]) {

int temp = arr[i];

arr[i] = arr[i+1];

arr[i+1] = temp;

sortedFlag = 1;

}

}

// 该趟排序中没有发生，表示已经有序

if (0 == sortedFlag) {

break;

}

}

}

2.1.

3. 算法分析

?冒泡排序是原地排序。因为冒泡过程中只涉及到相邻数据的交换，相当于只需要开辟一个内存空间用来完成相邻的数据交换即可。

?在元素大小相等的时候，不进行交换，那么冒泡排序就是稳定的排序算法。

?冒泡排序的时间复杂度。

?当元素已经是排序好了的，那么最好情况的时间复杂度是O(n)。因为只需要跑一趟，然后发现已经排好序了，那么就可以退出了。

?当元素正好是倒序排列的，那么需要进行n-1趟排序，最坏情况复杂度为O(n^2)。

?一般情况下，平均时间复杂度是O(n^2)。使用有序度和逆序度的方法来求时间复杂度，冒泡排序过程中主要是两个操作：比较和交换。每交换一次，有序度就增加一，因此有序度增加的次数就是交换的次数。又因为有序度需要增加的次数等于逆序度，所以交换的次数其实就等于逆序度。

因此当要对包含n个数据的数组进行冒泡排序时。最坏情况下，有序度为0，那么需要进行

n*(n-1)/2次交换；最好情况下，不需要进行交换。

我们取中间值n*(n-1)/4，来表示初始有序度不是很高也不是很低的平均情况。由于平均情况下需要进行n*(n-1)/4次交换，比较操作肯定比交换操作要多。

但是时间复杂度的上限是O(n^2)，所以平均情况下的时间复杂度就是O(n^2)。

这种方法虽然不严格，但是很实用。主要是因为概率的定量分析太复杂，不实用。（P S：我就喜欢这种

的）

”

2.2. 插入排序

插入排序中将数组中的元素分成两个区间：已排序区间和未排序区间（最开始的时候已排序区间的元

素只有数组的第一个元素），插入排序就是将未排序

区间的元素依次插入到已排序区间（需要保持已排序

区间的有序）。最终整个数组都是已排序区间，即排

序好了。**假设要对n个元素进行排序，那么未排序区间的元素个数为n-1，因此需要n-1次插入。插

入位置的查找可以从尾到头遍历已排序区间也可以从

头到尾遍历已排序区间。

如图所示，假设要对4、5、6、1、3、2进行排序。左侧橙红色表示的是已排序区间，右侧黄色的表

示未排序区间。整个插入排序过程如下所示

2.2.1. 优化

?采用希尔排序的方式。

?**使用哨兵机制。**比如要排序的数组是[2、1、3、4]，为了使用哨兵机制，首先需要将数组的第 0 位空出来，然后数组元素全都往后移动一格，变成[0、

2、1、

3、4]。那么数组 0 的位置用来存放要插入的数据，这样一来，判断条

件就少了一个，不用再判断 j >= 0 这个条件了，只需要使用 arr[j] >

arr[0] 的条件就可以了。因为就算遍历到下标为 0 的位置，由于 0 处这个值跟要插入的值是一样的，所以会退出循环，不会出现越界的问题。

2.2.2. 实现

这边查找插入位置的方式采用从尾到头遍历已排序区间，也没有使用哨兵。

/**

* 插入排序：

* 插入排序也相当于把待排序序列分成已排序区和未排序区；

* 每趟排序都将从未排序区选择一个元素插入到已排序合适的位置；

* 假设第一个元素属于已排序区，那么还需要插入 len-1 趟；

*/

public void insertSort(int[] arr, int len) {

// len-1 趟

for (int i = 1; i < len; i++) {

// 一趟排序

int temp = arr[i];

int j;

for (j = i-1; j >= 0; j--) {

if (arr[j] > temp) {

arr[j+1] = arr[j];

} else {

break;

}

}

arr[j+1] = temp;

}

}

2.2.

3. 算法分析

?插入排序是原地算法。因为只需要开辟一个额外的存储空间来临时存储元素。

?当比较元素时发现元素相等，那么插入到相等元素的后面，此时就是稳定排序。也就是说只有当有序区间中的元素大于要插入的元素时才移到到后面的位置，不大于（小于等于）了的话直接插入。

?插入排序的时间复杂度。

?待排序的数据是有序的情况下，不需要搬移任何数据。那么采用从尾到头在已排序区间中查找插入位置的方式，最好时间复杂度是O(n)。

?待排序的数据是倒序的情况，需要依次移动1、2、

3、...、n-1个数据，因此最坏时间复杂度是

O(n^2)。

?平均时间复杂度是O(n^2)。因此将一个数据插入到一个有序数组中的平均时间度是O(n)，那么需要插入

n-1个数据，因此平均时间复杂度是O(n^2)

最好的情况是在这个数组中的末尾插入元素的话，不需要移动数组，时间复杂度是O(1)，假如在数组开头插入数据的话，那么所有的数据都需要依次往后移动一位，所以时间复杂度是O(n)。往数组第k个位置插入的话，那么k~n这部分的元素都需要往后移动一位。

因此此时插入的平均时间复杂度是O(n)。

2.2.4. VS 冒泡排序

冒泡排序和插入排序的时间复杂度都是O(n^2)，

都是原地稳定排序。而且冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码的实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要一个赋值

操作。所以，虽然冒泡排序和插入排序在时间复杂度上都是O(n^2)，但是如果希望把性能做到极致，首选插

入排序。其实该点分析的主要出发点就是在同阶复杂度下，需要考虑系数、常数、低阶等。

2.3. 选择排序

选择排序也分为已排序区间和未排序区间（刚开始的已排序区间没有数据），选择排序每趟都会从未排序区间中找到最小的值（从小到大排序的话）放到已排序区间的末尾。

2.3.1. 实现

/**

* 选择排序：

* 选择排序将待排序序列分成未排序区和已排序区；

* 第一趟排序的时候整个待排序序列是未排序区；

* 每一趟排序其实就是从未排序区选择一个最值，放到已排序区；

* 跑 len-1 趟就好

*/

public void switchSort(int[] arr, int len) {

// len-1 趟，0-i 为已排序区

for (int i = 0; i < len-1; i++) {

int minIndex = i;

for (int j = i+1; j < len; j++) {

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

}

if (minIndex != i) {

int temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

}

}

2.3.2. 算法分析

?选择排序是原地排序，因为只需要用来存储最小值所处位置的额外空间和交换时所需的额外空间。

?选择排序不是一个稳定的算法。因为选择排序是从未排序区间中找一个最小值，并且和前面的元素交换位置，这会破坏稳定性。比如 1、5、5、2 这样一组数据中，使用排序算法的话。当找到 2 为 5、5、2 当前未排序区间最小的元素时，2 会与第一个 5 交换位置，那么两个 5 的顺序就变了，就破坏了稳定性。

?时间复杂度分析。最好、最坏、平均都是 O(n^2)，因为无论待排序数组情况怎么样，就算是已经有序了，都是需要依次遍历完未排序区间，需要比较的次数依次是 n-1、n-2，所以时间复杂度是 O(n^2)。

2.4. 归并排序（Merge Sort）

归并排序的核心思想就是我要对一个数组进行排序：首先将数组分成前后两部分，然后对两部分分别

进行排序，排序好之后再将两部分合在一起，那整个

数组就是有序的了。对于分出的两部分可以采用相同

的方式进行排序。**这个思想就是分治的思想，就是先将大问题分解成小的子问题来解决，子问题解决之后，大问题也就解决了。而对于子问题的求解也是一样的套路。这个套路有点类似于递归的方式，所以分治算法一般使用递归来实现。分治是一种解决问题的处理思想，而递归是一种实现它的编程方法。

2.4.1. 实现

下面使用递归的方式来实现归并排序。递归的递推公式是：m e r g e_s o r t(p...r)=

m e r g e(m e r g e_s o r t(p...q),m e r g e_s o r t(q+1...r))，终止条件是p>=r，不再递归下去了。整个实现过程是先调用__m e r g e S o r t()函数将两部分分别排好序，之后再使用数组合并的方式将两个排序好的部分进行合并。

/**

* 归并排序

*/

public void mergeSort(int[] arr, int len) {

__mergerSort(arr, 0, len-1);

}

private void __mergerSort(int[] arr, int begin, int end) {

if (begin == end){

return;

}

__mergerSort(arr, begin, (begin+end)/2);

__mergerSort(arr, (begin+end)/2 + 1, end);

merge(arr, begin, end);

return;

}

private void merge(int[] arr, int begin, int end) {

int[] copyArr = new int[end-begin+1];

System.arraycopy(arr, begin, copyArr, 0, end-begin+1);

int mid = (end - begin + 1)/2;

int i = 0; // begin - mid 的指针

int j = mid; // mid - end 的指针

int count = begin; // 合并之后数组的指针

while (i <= mid-1 && j <= end - begin) {

arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];

}

while (i <= mid-1) {

arr[count++] = copyArr[i++];

}

while (j <= end - begin) {

arr[count++] = copyArr[j++];

}

}

2.4.2. 算法分析

?归并排序可以是稳定的排序算法，只要确保合并时，如果遇到两个相等值的，前半部分那个相等的值是在后半部分那个相等的值的前面即可保证是稳定的排序算法。

?归并排序的时间复杂度为O(n l o g n)，无论是最好、最坏还是平均情况都一样。

归并的时间复杂度分析则是递归代码的时间复杂度的分析。假设求解问题a可以分为对b、c两个子问题的求解。那么问题a的时间是T(a)、求解

b、c的时间分别是T(b)和T(c)，那么T(a)=

T(b)+T(c)+K。k等于将b、c两个子问题的结果合并问题a所消耗的时间。

套用上述的套路，假设对n个元素进行归并排序需要的时间是T(n)，子问题归并排序的时间是

T(n/2)，合并操作的时间复杂度是O(n)。所以，T(n) =2*T(n/2)+O(n)，T(1)=C。最终得到：

T(n)= 2*T(n/2) + n

= 2*(2*T(n/4)+ n/2)+n = 2^2*T(n/4) + 2*n

= 2^2*(2*T(n/8)+n/4) + 2*n = 2^3*T(n/8) + 3*n

= ....

= 2^k*T(n/2^K) + k*n

= ....

= 2^(log_2^n)*T(1) + log_2^n*n

最终得到，使用大O时间复杂表示

T(n)=O(n l o g n)。

归并排序中，无论待排数列是有序还是倒序，最终递归的层次都是到只有一个数组为主，所以归并排序跟

待排序列没有什么关系，最好、最坏、平均的时间复杂度都是O(n l o g n)。

?归并排序并不是原地排序，因为在归并排序的合并函数中，还需要额外的存储空间，这个存储空间是

O(n)。递归过程中，空间复杂度并不能像时间复杂度

那样累加。因为在每次递归下去的过程中，虽然合并

操作都会申请额外的内存空间，但是合并之后，这些

申请的内存空间就会被释放掉。因此其实主要考虑最

大问题合并时所需的空间复杂度即可，该空间复杂度

为O(n)。

2.5. 快速排序（Quick Sort）

快速排序利用的也是分治思想，核心思想是从待排数组中选择一个元素，然后将待排数组划分成两个部

分：左边部分的元素都小于该元素的值，右边部分的元素都大于该元素的值，中间是该元素的值。然后对左右两个部分套用相同的处理方法，也就是将左边部分的元素再划分成左右两部分，右边部分的元素也再划分成左右两部分。以此类推，当递归到只有一个元素的时候，就说明此时数组是有序了的。

2.5.1. 实现

首先要对下标从 begin 到 end 之间的数据进行分区，可以选择 begin 到 end 之间的任意一个数据作为 pivot（分区点），一般是最后一个数据作为分区点。之后遍历 begin 到 end 之间的数据，将小于 pivot 的放在左边，大于的 pivot 的放在右边，将pivot 放在中间（位置 p）。经过这一操作之后，数组 begin 到 end 之间的数据就被分成了三个部分：begin 到 p-

1、p、p+1 到 end。最后，返回 pivot 的下标。那么这个过程一般有三种方

式：

?首先说明这种方法不可取。在不考虑空间消耗的情况下，分区操作可以非常简单。使用两个临时数组 X 和 Y，遍历 begin 到 end 之间的数据，将小于pivot 的数据都放到数组 X 中，将大于 pivot 的数据都放到数组 Y 中，最后将数组 X 拷贝到原数组中，然后再放入 pivot，最后再放入数组 Y。但是采用这种方式之后，快排就不是原地排序算法了，因此可以采用以下两种方法在原数组的基础之上完成分区操作。

?第一种方法还是使用两个指针：i 和 j，i 和 j 一开始都放置在 begin 初。

之后 j 指针开始遍历，如果 j 指针所指的元素小于等于 pivot，那么则将 j 指针的元素放到 i 指针的处，i 指针的元素放置于 j 处，然后 i 后移，j 后移。如果 j 指针所指的元素大于 pivot 那么 j 后移即可。首先个人觉得其实整个数组被分成三个区域：0-i-1 的为小于等于 pivot 的区域，i-j-1 为大于 pivot 的区域，j 之后的区域是未排序的区域。

?第二种方法还是使用两个指针：i 和 j，i 从 begin 处开始，j 从 end 处开始。首先 j 从 end 开始往前遍历，当遇到小于 pivot 的时候停下来，然后此

时 i 从 begin 开始往后遍历，当遇到大于 pivot 的时候停下来，此时交换 i 和 j 处的元素。之后 j 继续移动，重复上述过程，直至 i >= j。

在返回 pivot 的下标 q 之后，再根据分治的思想，将 begin 到 q-1

之间的数据和下标 q+1 到 end 之间的数据进行递归。这边一定要 q-1 和

q+1 而不能是 q 和 q+1 是因为：考虑数据已经有序的极端情况，一开始是

对 begin 到 end；当分区之后 q 的位置还是 end 的位置，那么相当于死循

环了。最终，当区间缩小至 1 时，说明所有的数据都有序了。

如果用递推公式来描述上述的过程的话，递推公式：

quick_sort(begin...end) = quick_sort(begin...q-1) +

quick_sort(q+1...end)，终止条件是：begin >= end。将这两个公式转化为

代码之后，如下所示：

/**

* 快速排序

*/

public void quickSort(int[] arr, int len) {

__quickSort(arr, 0, len-1);

}

// 注意边界条件

private void __quickSort(int[] arr, int begin, int end) {

if (begin >= end) {

return;

}

// 一定要是 p-1！

int p = partition(arr, begin, end); // 先进行大致排序，并获取区分点

__quickSort(arr, begin, p-1);

__quickSort(arr, p+1, end);

}

private int partition(int[] arr, int begin, int end) {

int pValue = arr[end];

// 整两个指针，两个指针都从头开始

// begin --- i-1（含 i-1）：小于 pValue 的区

// i --- j-1（含 j-1）：大于 pValue 的区

// j --- end：未排序区

int i = begin;

int j = begin;

while (j <= end) {

if (arr[j] <= pValue) {

int temp = arr[j];

arr[j] = arr[i];

arr[i] = temp;

i++;

j++;

} else {

j++;

}

}

return i-1;

}

2.5.2. 优化

?由于分区点很重要（为什么重要见算法分析），因此可以想方法寻找一个好的分区点来使得被分区点分开的两个分区中，数据的数量差不多。下面介绍两种比较常见的算法：

?**三数取中法。就是从区间的首、尾、中间分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。**但是，如果排序的数组比较大，那“三数取中”可能不够了，可能就要“五数取中”或者“十数取中”，也就是间隔某个固定的长度，取数据进行比较，然后选择中间值最为分区点。

?随机法。随机法就是从排序的区间中，随机选择一个元素作为分区点。随机法不能保证每次分区点都是比较好的，但是从概率的角度来看，也不太可能出现每次分区点都很差的情况。所以平均情况下，随机法取分区点还是比较好的。?递归可能会栈溢出，最好的方式是使用非递归的方式；

2.5.

3. 算法分析

?快排不是一个稳定的排序算法。因为分区的过程涉及到交换操作，原本在前面的元素可能会被交换到后面

去。比如6、8、7、6、3、5、9、4这个数组中。在

经过第一次分区操作之后，两个6的顺序就会发生改变。

?快排是一种原地的排序算法。

?快排的最坏时间复杂度是O(n^2)，最好时间复杂度是O(n l o g n)，平均时间复杂度是O(n l o g n)。

快排也是使用递归来实现，那么递归代码的时间复杂

度处理方式和前面类似。

快排的时间复杂度取决于p i v o t的选择，通过合理地选择p i v o t来使得算法的时间复杂度尽可能不出现

O(n^2)的情况。

?假设每次分区操作都可以把数组分成大小接近相等的两个小区间，那么快排的时间复杂度和归并排序一样，都是 O(nlogn)。

?但是分区操作不一定都能把数组分成大小接近相等的两个小区间。极端情况如数组中的数组已经有序了，如果还是取最后一个元素作为分割点，左边区间是n-1 个数，右边区间没有任何数。此时， T(n)=T(n-1)+n，最终时间复杂度退化为 O(n^2)。大部分情况下，采用递归树的方法可得到时间复杂度是

O(nlogn)。由于极端情况是少数，因此平均时间复杂度是 O(nlogn)。

2.5.4. VS 归并排序

首先从思想上来看：归并排序的处理过程是由下到上的，先处理子问题，然后对子问题的解再合并；而快排正好相反，处理过程是由上到下的，先分区，再处理子问题。

从性能上来看：归并是一个稳定的、时间复杂度为O(n l o g n)的排序算法，但是归并并不是一个原地排序算法（所以归并没有快排应用广泛）。而快速排序算法时间复杂度不一定是O(n l o g n)，最坏情况下是

O(n^2)，而且不是一个稳定的算法，但是通过设计可以让快速排序成为一个原地排序算法。

2.6. 桶排序

桶排序的核心思想就是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。**桶内排序完成之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。一般步骤是：

?先确定要排序的数据的范围；

?然后根据范围将数据分到桶中（可以选择桶的数量固定，也可以选择桶的大小固定）；

?之后对每个桶进行排序；

?之后将桶中的数据进行合并；

2.6.1. 实现

public void buckerSort(int[] arr, int len, int bucketCount) {

// 确定数据的范围

int minVal = arr[0];

int maxVal = arr[0];

for (int i = 1; i < len; ++i) {

if (arr[i] < minVal) {

minVal = arr[i];

} else if (arr[i] > maxVal){

maxVal = arr[i];

}

}

// 确认每个桶的所表示的范围

bucketCount = (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount;

int bucketSize = (maxVal - minVal + 1) / bucketCount;

bucketCount = (maxVal - minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;

int[][] buckets = new int[bucketCount][bucketSize];

int[] indexArr = new int[bucketCount]; // 数组位置记录

// 将数据依次放入桶中

for (int i = 0; i < len; i++) {

int bucketIndex = (arr[i] - minVal) / bucketSize;

if (indexArr[bucketIndex] == buckets[bucketIndex].length) { expandCapacity(buckets, bucketIndex);

}

buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];

}

// 桶内排序

for (int i = 0; i < bucketCount; ++i) {

if (indexArr[i] != 0) {

quickSort(buckets[i], 0, indexArr[i] - 1);

}

}

// 桶内数据依次取出

int index = 0;

for (int i = 0; i < bucketCount; ++i) {

for (int j = 0; j < indexArr[i]; ++j) {

arr[index++] = buckets[i][j];

}

}

// 打印

for (int i = 0; i < len; ++i) {

System.out.print(arr[i] + " ");

}

System.out.println();

}

// 对数组进行扩容

public void expandCapacity(int[][] buckets, int bucketIndex) {

int[] newArr = new int[buckets[bucketIndex].length * 2];

System.arraycopy(buckets[bucketIndex], 0, newArr, 0,

buckets[bucketIndex].length);

buckets[bucketIndex] = newArr;

}

2.6.2. 算法分析

?最好时间复杂度为O(n)，最坏时间复杂度为O(n l o g n)，平均时间复杂度为O(n)。

如果要排序的数据为n个，把这些数据均匀地分到m个桶内，每个桶就有k=n/m个元素。每个桶使用快速排序，时间复杂度为O(k.l o g k)。m个桶的时间复杂度就是O(m*k*l o g k)，转换的时间复杂度就是

O(n*l o g(n/m))。当桶的数量m接近数据个数n

时，l o g(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度接近O(n)。

?如果数据经过桶的划分之后，每个桶的数据很不平均，比如一个桶中包含了所有数据，那么桶排序就退

化为O(n l o g n)的排序算法了。

?这边的平均时间复杂度为O(n)没有经过严格运算，只是采用粗略的方式得出的。因为桶排序大部分情况

下，都能将数据进行大致均分，而极少情况出现所有

的数据都在一个桶里。

?非原地算法

?因为桶排序的过程中，需要创建m个桶这个的空间复杂度就肯定不是O(1)了。在桶内采用快速排序的情

况下，桶排序的空间复杂度应该是O(n)。

?桶排序的稳定与否，主要看两块：1.将数据放入桶中的时候是否按照顺序放入；2.桶内采用的排序算法。

所以将数据放入桶中是按照顺序的，并且桶内也采用

稳定的排序算法的话，那么整个桶排序则是稳定的。

既然能稳定的话，那么一般算稳定的。

2.6.

3. 总结

?桶排序对要排序的数据的要求是非常苛刻的。

?首先，要排序的数据需要很容易被划分到 m 个桶。并且，桶与桶之间有着天然的大小顺序，这样子每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序；

?其次，数据在各个桶中的分布是比较均匀的。如果数据经过桶的划分之后，每个桶的数据很不平均，比如

一个桶中包含了所有数据，那么桶排序就退化为

O(n l o g n)的排序算法了。

?桶排序适合应用在外部排序中。比如要排序的数据有10G B的订单数据，但是内存只有几百M B，无法一次性把10G B的数据全都加载到内存中。这个时候，就

可以先扫描10G B的订单数据，然后确定一下订单数

据的所处的范围，比如订单的范围位于1~10万元之

间，那么可以将所有的数据划分到100个桶里。再依次扫描10G B的订单数据，把1~1000元之内的订单存放到第一个桶中，1001~2000元之内的订单数据存

放到第二个桶中，每个桶对应一个文件，文件的命名

按照金额范围的大小顺序编号如00、01，即第一个桶的数据输出到文件00中。

?理想情况下，如果订单数据是均匀分布的话，每个文件的数据大约是100M B，依次将这些文件的数据读取

到内存中，利用快排来排序，再将排序好的数据存放

回文件中。最后只要按照文件顺序依次读取文件中的

数据，并将这些数据写入到一个文件中，那么这个文

件中的数据就是排序好了的。

?但是，订单数据不一定是均匀分布的。划分之后可能还会存在比较大的文件，那就继续划分。比如订单金

额在1~1000元之间的比较多，那就将这个区间继续

划分为10个小区间，1~100、101~200等等。如果

划分之后还是很大，那么继续划分，直到所有的文件

都能读入内存。

?外部排序就是数据存储在磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

2.7. 计数排序

计数排序跟桶排序类似，可以说计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 K，那么就可以把数据划分到 K 个桶，每个桶内的数据值都是相同的，从而省掉了桶内排序的时间。可以说计数排序和桶排序的区别其实也就在于桶的大小粒度不一样。

下面通过举例子的方式来看一下计数排序的过程。假设数组 A 中有 8 个数据，值在 0 到 5 之间，分别是：2、5、3、0、2、3、0、3。

?首先使用大小为 6 的数组 C[6] 来存储每个值的个数，下标对应具体值。从而得到，C[6] 的情况为：2、0、2、3、0、1。

?那么，值为 3 分的数据个数有 3 个，小于 3 分的数据个数有 4 个，所以值为 3 的数据在有序数组 R 中所处的位置应该是 4、5、6。为了快速计算出位置，对 C[6] 这个数组进行变化，C[k] 里存储小于等于值 k 的数据个数。变化之后的数组为 2、2、4、7、7、8。

?之后我们从后往前依次扫描数据 A（从后往前是为了稳定），比如扫描到 3 的时候，从数据 C 中取出下标为 3 的值，是7（也就说到目前为止，包含自己在内，值小于等于 3 的数据个数有 7 个），那么 3 就是数组 R 中第 7 个元素，也就是下标为 6。当然 3 放入到数组 R 中后，C[3] 要减 1，变成 6，表示此时未排序的数据中小于等于 3 的数据个数有 6 个。

?以此类推，当扫描到第 2 个值为 3 的数据的时候，就会将这个数据放入到 R 中下标为 5 的位置。当扫描完整个数组 A 后，数组 R 内的数据就是按照值从小到大的有序排列了。

2.7.1. 实现

/**

* 计数排序，暂时只能处理整数（包括整数和负数）

* @param arr

* @param len

*/

public void countingSort(int[] arr, int len) {

// 确定范围

int minVal = arr[0];

int maxVal = arr[0];

for (int i = 1; i < len; ++i) {

if (maxVal < arr[i]) {

maxVal = arr[i];

} else if (arr[i] < minVal) {

minVal = arr[i];

}

}

// 对数据进行处理

for (int i = 0; i < len; ++i) {

arr[i] = arr[i] - minVal;

}

maxVal = maxVal - minVal;

// 遍历数据数组，求得计数数组的个数

int[] count = new int[maxVal + 1];

for (int i = 0; i < len; ++i) {

count[arr[i]] ++;

}

printAll(count, maxVal + 1);

// 对计数数组进行优化

for (int i = 1; i < maxVal + 1; ++i) {

count[i] = count[i - 1] + count[i];

}

printAll(count, maxVal + 1);

// 进行排序，从后往前遍历（为了稳定）

int[] sort = new int[len];

for (int i = len - 1; i >= 0; --i) {

sort[count[arr[i]] - 1] = arr[i] + minVal;

count[arr[i]]--;

}

printAll(sort, len);

}

2.7.2. 算法分析

?非原地算法

计数排序相当于桶排序的特例一样。计数排序需要额外的 k 个内存空间和n 个新的内存空间存放排序之后的数组。

各种排序算法比较

排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76]

C语言几种常见的排序方法

C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序 选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

几种排序算法分析

《几种排序算法的分析》 摘要: 排序算法是在C++中经常要用到的一种重要的算法。如何进行排序，特别是高效率的排序是是计算机应用中的一个重要课题。同一个问题可以构造不同的算法，最终选择哪一个好呢？这涉及如何评价一个算法好坏的问题，算法分析就是评估算法所消耗资源的方法。可以对同一问题的不同算法的代价加以比较，也可以由算法设计者根据算法分析判断一种算法在实现时是否会遇到资源限制的问题。排序的目的之一就是方便数据的查找。在实际生活中，应根据具体情况悬着适当的算法。一般的，对于反复使用的程序，应选取时间短的算法；对于涉及数据量较大，存储空间较小的情况则应选取节约存储空间的算法。本论文重点讨论时间复杂度。时间复杂度就是一个算法所消耗的时间。算法的效率指的是最坏情况下的算法效率。 排序分为内部排序和外部排序。本课程结业论文就内部排序算法（插入排序，选择排序，交换排序，归并排序和基数排序）的基本思想，排序步骤和实现算法等进行介绍。 本论文以较为详细的文字说明，表格对比，例子阐述等方面加以比较和总结，通过在参加数据的规模，记录说带的信息量大小，对排序稳定的要求，关键字的分布情况以及算法的时间复杂度和空间复杂度等方面进行比较，得出它们的优缺点和不足，从而加深了对它们的认识和了解，进而使自己在以后的学习和应用中能够更好的运用。

1.五种排序算法的实例： 1.1.插入排序 1.1.1.直接插入排序 思路：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。 要点：设立哨兵，作为临时存储和判断数组边界之用。 实现： Void InsertSort(Node L[],int length) { Int i,j;//分别为有序区和无序区指针 for(i=1;i=1)//直到增量缩小为1 { Shell(L,d); d=d/2;//缩小增量 } } Void Shell(Node L[],int d) {

各种排序算法的总结和比较

各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort）

归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。

几种常见内部排序算法比较

常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.

详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key

几种排序算法的平均性能比较(实验报告)

实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于围（0，105）的整数。 对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）： 选择排序：令A[1…n]为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序， 即对啊[A…n]排序。对某个j,1<=j<=n,设A[j]是最小值。首先，如果就！=1，我们交换A[1] 和A[j]。然后由假设，已知如何对A[2..n]排序，因此可对在A[2…n]中的元素递归地排序。 可把递归改为迭代。算法程序实现如下： void SelectionSort(int *Array,int n,int &c) { int i,j,k; int aa; c=0; for(i=0;i

五种排序算法的分析与比较

五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词：冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1]，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2，3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想

冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至ｎ-1个记录和第ｎ个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过ｎ-1次比较,不需要移动关键字,即时间复杂度为Ｏ(ｎ)(即正序);在最坏情况下是初始序列为逆序,则需要进行ｎ-1次排序,需进行ｎ(ｎ-1)/2次比较,因此在最坏情况下时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是ｎ个记录的文件的直接排序可经过ｎ-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(ｎ-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为ｎ(ｎ-1)/2,时间

常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排

常见经典排序算法（C语言） 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法*/ #include void sort(int v[],int n) { int gap,i,j,temp; for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ { for(i=gap;i= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换*/ { temp=v[j]; v[j]=v[j+gap]; v[j+gap]=temp; } }

} } 二.二分插入法 /* 二分插入法*/ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i temp) /* 如果中间元素比但前元素大，当前元素要插入到中间元素的左侧*/ { high = mid-1; } else /* 如果中间元素比当前元素小，但前元素要插入到中间元素的右侧*/ { low = mid+1; } } /* 找到当前元素的位置，在low和high之间*/ for (j=i-1; j>high; j--)/* 元素后移*/ { a[j+1] = a[j]; } a[high+1] = temp; /* 插入*/ } }

数据结构各种排序算法的时

数据结构各种排序算法的时间性能.

HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能 学生姓名 学生学号 专业班级

指导老师李晓鸿完成日期

设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略

十 大 经 典 排 序 算 法 总 结 超 详 细

数据挖掘十大经典算法，你都知道哪些？ 当前时代大数据炙手可热，数据挖掘也是人人有所耳闻，但是关于数据挖掘更具体的算法，外行人了解的就少之甚少了。 数据挖掘主要分为分类算法，聚类算法和关联规则三大类，这三类基本上涵盖了目前商业市场对算法的所有需求。而这三类里又包含许多经典算法。而今天，小编就给大家介绍下数据挖掘中最经典的十大算法，希望它对你有所帮助。 一、分类决策树算法C4.5 C4.5，是机器学习算法中的一种分类决策树算法，它是决策树(决策树，就是做决策的节点间的组织方式像一棵倒栽树)核心算法ID3的改进算法，C4.5相比于ID3改进的地方有： 1、用信息增益率选择属性 ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（shang），一种不纯度度量准则，也就是熵的变化值，而 C4.5用的是信息增益率。区别就在于一个是信息增益，一个是信息增益率。 2、在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟。 3、能对非离散数据和不完整数据进行处理。 该算法适用于临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。 二、K平均算法

K平均算法（k-means algorithm）是一个聚类算法，把n个分类对象根据它们的属性分为k类（kn）。它与处理混合正态分布的最大期望算法相似，因为他们都试图找到数据中的自然聚类中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 k-Means 算法常用于图片分割、归类商品和分析客户。 三、支持向量机算法 支持向量机(Support Vector Machine)算法，简记为SVM，是一种监督式学习的方法，广泛用于统计分类以及回归分析中。 SVM的主要思想可以概括为两点： (1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分； (2)它基于结构风险最小化理论之上，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。 四、The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段“频繁项集”思想的递推算法。其涉及到的关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支

C#实现所有经典排序算法

C#实现所有经典排序算法 //选择排序 class SelectionSorter { private int min; public void Sort(int[] arr) { for (int i = 0; i < arr.Length - 1; ++i) { min = i; for (int j = i + 1; j < arr.Length; ++j) { if (arr[j] < arr[min]) min = j; } int t = arr[min]; arr[min] = arr[i]; arr[i] = t; } } static void Main(string[] args) { int[] array = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 }; SelectionSorter s = new SelectionSorter(); s.Sort(array); foreach (int m in array) Console.WriteLine("{0}", m); } } //冒泡排序 class EbullitionSorter { public void Sort(int[] arr) { int i, j, temp; bool done = false; j = 1; while ((j < arr.Length) && (!done))//判断长度 { done = true; for (i = 0; i < arr.Length - j; i++) { if (arr[i] > arr[i + 1]) {

常用排序算法比较与分析报告

常用排序算法比较与分析 一、常用排序算法简述 下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。依据待排序的问题大小(记录数量 n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【排序】、【外排序】。 排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。 外排序：待排序记录的数量很大，以致存一次不能容纳全部记录，在排序过程中还需要对外存进行访问的排序过程。 先了解一下常见排序算法的分类关系(见图1-1) 图1-1 常见排序算法 二、排序相关算法 2.1 插入排序 核心思想：将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。 2.1.1 直接插入排序 核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、… 数据元素的值进行顺序比较，通过这种线性搜索的方法找到第i个数据元素的插入位置，并且原来位置的数据元素顺序后移，直到全部排好顺序。 直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。

Python源代码： 1.#-------------------------直接插入排序-------------------------------- 2.def insert_sort(data_list): 3.#遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始 4.for x in range(1, len(data_list)): 5.#将该元素与已排序好的前序数组依次比较，如果该元素小，则交换 6.#range(x-1,-1,-1):从x-1倒序循环到0 7.for i in range(x-1, -1, -1): 8.#判断：如果符合条件则交换 9.if data_list[i] > data_list[i+1]: 10.temp= data_list[i+1] 11.data_list[i+1] = data_list[i] 12.data_list[i] = temp 2.1.2 希尔排序 核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。 Python源代码： 1.#-------------------------希尔排序------------------------------- 2.def insert_shell(data_list): 3.#初始化step值，此处利用序列长度的一半为其赋值 4.group= int(len(data_list)/2) 5.#第一层循环：依次改变group值对列表进行分组 6.while group> 0: 7.#下面：利用直接插入排序的思想对分组数据进行排序 8.#range(group,len(data_list)):从group开始 9.for i in range(group, len(data_list)): 10.#range(x-group,-1,-group):从x-group开始与选定元素开始倒序比较，每个比较元素之间间隔group 11.for j in range(i-group, -1, -group): 12.#如果该组当中两个元素满足交换条件，则进行交换 13.if data_list[j] > data_list[j+group]: 14.temp= data_list[j+group] 15.data_list[j+group] = data_list[j] 16.data_list[j] = temp 17.#while循环条件折半 18.group= int(group/ 2) 2.2 选择排序

各种排序算法总结

各种排序算法总结 排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准： （）执行时间 （）存储空间 （）编程工作 对于数据量较小的情形，（）（）差别不大，主要考虑（）；而对于数据量大的，（）为首要。主要排序法有： 一、冒泡（）排序——相邻交换 二、选择排序——每次最小大排在相应的位置 三、插入排序——将下一个插入已排好的序列中 四、壳（）排序——缩小增量 五、归并排序 六、快速排序 七、堆排序 八、拓扑排序 九、锦标赛排序 十、基数排序 一、冒泡（）排序 从小到大排序个数 () { ( <) { ( <) { ([]>[])比较交换相邻元素 { ; []; [][]; []; } } } } 效率（2）,适用于排序小列表。 二、选择排序 从小到大排序个数

{ ; ( <) { ; ( <)每次扫描选择最小项 ([]<[]) ; ()找到最小项交换，即将这一项移到列表中的正确位置 { ; []; [][]; []; } } } 效率（2），适用于排序小的列表。 三、插入排序 从小到大排序个数 () { ( <)循环从第二个数组元素开始，因为[]作为最初已排序部分 { []标记为未排序第一个元素 ; (> []>)*将与已排序元素从小到大比较，寻找应插入的位置* { [][]; ; } []; } } 最佳效率（）；最糟效率（2）与冒泡、选择相同，适用于排序小列表若列表基本有序，则插入排序比冒泡、选择更有效率。 四、壳（）排序——缩小增量排序 从小到大排序个数

{ ( <)增量递减 { ( <())重复分成的每个子列表 { ( <)对每个子列表应用插入排序 { []; ; (>[]>) { [][]; ; } []; } } } } 适用于排序小列表。 效率估计（^）（^），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是的幂，则在下一个通道中会再次比较相同的元素。 壳（）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。 五、归并排序 从小到大排序 ( ) { (>) 每个子列表中剩下一个元素时停止 ()*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表* ()子列表进一步划分 (); [] []新建一个数组，用于存放归并的元素 ( < <)*两个子列表进行排序归并，直到两个子列表中的一个结束* { ([]<[];) { [][];

几种排序算法的分析与比较--C语言

一、设计思想 插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。 选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。 希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算

十大经典排序算法

.1 算法分类 十种常见排序算法可以分为两大类： ?比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 ?非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 0.2 算法复杂度

0.3 相关概念 ?稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。 ?不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。 ?时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。 ?空间复杂度：是指算法在计算机 内执行时所需存储空间的度量，它也是数据规模n的函数。 1、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述 ?比较相邻的元素。如果第一个比第二个大，就交换它们两个； ?对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； ?针对所有的元素重复以上的步骤，除了最后一个； ?重复步骤1~3，直到排序完成。 1.2 动图演示 1.3 代码实现 ?

2、选择排序（Selection Sort） 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 2.1 算法描述 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下： ?初始状态：无序区为R[1..n]，有序区为空； ?第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区； ?n-1趟结束，数组有序化了。 2.2 动图演示 2.3 代码实现 ?

数据结构中几种常见的排序算法之比较

几种常见的排序算法之比较 2010-06-20 14:04 数据结构课程 摘要： 排序的基本概念以及其算法的种类，介绍几种常见的排序算法的算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度，然后以表格的形式，清晰直观的表现出它们的复杂度的不同。在研究学习了之前几种排序算法的基础上，讨论发现一种新的排序算法，并通过了进一步的探索，找到了新的排序算法较之前几种算法的优势与不足。 关键词：排序算法复杂度创新算法 一、引言 排序算法，是计算机编程中的一个常见问题。在日常的数据处理中，面对纷繁的数据，我们也许有成百上千种要求，因此只有当数据经过恰当的排序后，才能更符合用户的要求。因此，在过去的数十载里，程序员们为我们留下了几种经典的排序算法，他们都是智慧的结晶。本文将带领读者探索这些有趣的排序算法，其中包括介绍排序算法的某些基本概念以及几种常见算法，分析这些算法的时间复杂度，同时在最后将介绍我们独创的一种排序方法，以供读者参考评判。 二、几种常见算法的介绍及复杂度分析 1.基本概念 1.1稳定排序(stable sort)和非稳定排序 稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 1.2内排序( internal sorting )和外排序( external sorting) 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

常见的八种经典排序方法

常见经典排序算法 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* Shell 排序法 */ #include void sort(int v[],int n) { int gap,i,j,temp; for(gap=n/2;gap>0;gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ { for(i=gap;i= 0) && (v[j] > v[j+gap]);j -= gap ) /* 比较相距gap远的两个元素的大小，根据排序方向决定如何调换 */ { temp=v[j];

v[j]=v[j+gap]; v[j+gap]=temp; } } } } 二.二分插入法 /* 二分插入法 */ void HalfInsertSort(int a[], int len) { int i, j,temp; int low, high, mid; for (i=1; i temp) /* 如果中间元素比但前元素大，当前元素要插入到中间元素的左侧 */