各种排序方法总结.docx
《各种排序方法总结.docx》由会员分享，可在线阅读，更多相关《各种排序方法总结.docx（26页珍藏版）》请在冰点文库上搜索。
各种排序方法总结
常用排序算法有哪些？
冒择路希快归堆（口诀）：
冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序；
冒泡排序
冒泡排序（BubbleSort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
publicclassBubbleSort
{
publicvoidsort（int[]a）
{
inttemp=0;
for（inti=a.length-1;i>0;--i）
{
for（intj=0;j{
if（a[j+1]{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
}
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
functionbubbleSort（arr）
{vari=arr.length,j;
vartempExchangVal;
while（i>0）
{
for（j=0;j{
if（arr[j]>arr[j+1]）
{
tempExchangVal=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tempExchangVal;
}
}
i--;
}
returnarr;
}vararr=[3,2,4,9,1,5,7,6,8];
vararrSorted=bubbleSort（arr）;
console.log（arrSorted）;
alert（arrSorted）;
控制台将输出：
[1,2,3,4,5,6,7,8,9]
快速排序算法
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C.A.R.Hoare在1962年提出。
它的基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Quick
{
public void sort（int arr[],int low,int high）
{
int l=low;
int h=high;
int povit=arr[low];
while（l {
while（l=povit）
h--;
if（l int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
l++;
}
while（l l++;
if（l int temp=arr[h];
arr[h]=arr[l];
arr[l]=temp;
h--;
}
}
print（arr）;
System.out.print（"l="+（l+1）+"h="+（h+1）+"povit="+povit+"\n"）;
if（l>low）sort（arr,low,l-1）;
if（h }
}
/*//////////////////////////方式二////////////////////////////////*/
更高效点的代码：
publicsuperT>>
T[]quickSort（T[]targetArr,intstart,intend）
{
inti=start+1,j=end;
Tkey=targetArr[start];
SortUtilsUtil=newSortUtil（）;
if（start>=end）return（targetArr）;
/*从i++和j--两个方向搜索不满足条件的值并交换
*
*条件为：
i++方向小于key，j--方向大于key
*/
while（true）
{
while（targetArr[j].compareTo（key）>0）j--;
while（targetArr[i].compareTo（key）<0&&iif（i>=j）break;
sUtil.swap（targetArr,i,j）;
if（targetArr[i]==key）
{
j--;
}else{
i++;
}
}
/*关键数据放到‘中间’*/
sUtil.swap（targetArr,start,j）;
if（start{
this.quickSort（targetArr,start,i-1）;
}
if（j+1{
this.quickSort（targetArr,j+1,end）;
}
returntargetArr;
}
/*//////////////方式三：
减少交换次数，提高效率/////////////////////*/
privatesuperT>>
voidquickSort（T[]targetArr,intstart,intend）
{
inti=start,j=end;
Tkey=targetArr[start];
while（i{
/*按j--方向遍历目标数组，直到比key小的值为止*/
while（j>i&&targetArr[j].compareTo（key）>=0）
{
j--;
}
if（i{
/*targetArr[i]已经保存在key中，可将后面的数填入*/
targetArr[i]=targetArr[j];
i++;
}
/*按i++方向遍历目标数组，直到比key大的值为止*/
while（i/*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。
*/
{
i++;
}
if（i{
/*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
targetArr[j]=targetArr[i];
j--;
}
}
/*此时i==j*/
targetArr[i]=key;
/*递归调用，把key前面的完成排序*/
this.quickSort（targetArr,start,i-1）;
/*递归调用，把key后面的完成排序*/
this.quickSort（targetArr,j+1,end）;
}
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function quickSort（array）{
function sort（prev, numsize）{
var nonius = prev;
var j = numsize -1;
var flag = array[prev];
if （（numsize - prev） > 1） {
while（nonius < j）{
for（; nonius < j; j--）{
if （array[j] < flag） {
array[nonius++] = array[j]; //a[i] = a[j]; i += 1;
break;
};
}
for（ ; nonius < j; nonius++）{
if （array[nonius] > flag）{
array[j--] = array[nonius];
break;
}
}
}
array[nonius] = flag;
sort（0, nonius）;
sort（nonius + 1, numsize）;
}
}
sort（0, array.length）;
return array;
}
选择排序
选择排序（Selectionsort）是一种简单直观的排序算法。
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法（比如序列[5，5，3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void selectSort（int[]a）
{
int minIndex=0;
int temp=0;
if（（a==null）||（a.length==0））
return;
for（int i=0;i {
minIndex=i;//无序区的最小数据数组下标
for（intj=i+1;j {
//在无序区中找到最小数据并保存其数组下标
if（a[j] {
minIndex=j;
}
}
if（minIndex!
=i）
{
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp=a[i];
a[i]=a[minIndex];
a[minIndex]=temp;
}
}
}
插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O（n^2）。
是稳定的排序方法。
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。
在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：
每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
Java版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
*插入排序
*@paramarr
*@return
*/
private static int[] insertSort（int[]arr）{
if（arr == null || arr.length < 2）{
return arr;
}
for（inti=1;ifor（intj=i;j>0;j--）{
if（arr[j]//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
//接下来是无用功
break;
}
}
}
return arr;
}
希尔排序
希尔排序（ShellSort）是插入排序的一种。
也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
希尔排序是非稳定排序算法。
该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public static void main（String [] args）
{
int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println（"排序之前：
"）;
for（int i=0;i {
System.out.print（a[i]+" "）;
}
//希尔排序
int d=a.length;
while（true）
{
d=d/2;
for（int x=0;x {
for（int i=x+d;i {
int temp=a[i];
int j;
for（j=i-d;j>=0&&a[j]>temp;j=j-d）
{
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
if（d==1）
{
break;
}
}
System.out.println（）;
System.out.println（"排序之后：
"）;
for（int i=0;i {
System.out.print（a[i]+" "）;
}
}
上面写的看的人头晕 我写个好理解的
while（true）{
for（int i=0;i for（int j=i;j+d int temp;
if（a[j]>a[j+d]）{
temp=a[j];
a[j]=a[j+d];
a[j+d]=temp;
}
}
}
if（d==1）{break;}
d--;
}
javascript
1
2
3
4
5
6
7
8
9
10
11
12
vararr=[49,38,65,97,76,13,27,49,55,04],
len=arr.length;
for（varfraction=Math.floor（len/2）;fraction>0;fraction=Math.floor（fraction/2））{
for（vari=fraction;ifor（varj=i-fraction;j>=0&&arr[j]>arr[fraction+j];j-=fraction）{
vartemp=arr[j];
arr[j]=arr[fraction+j];
arr[fraction+j]=temp;
}
}
}
console.log（arr）;
归并排序
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
归并过程为：
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
Java语言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package algorithm;
public class MergeSort {
// private static long sum = 0;
/**
*
* 二路归并
* 原理：
将两个有序表合并和一个有序表
*
*
* @param a
* @param s
* 第一个有序表的起始下标
* @param m
* 第二个有序表的起始下标
* @param t
* 第二个有序表的结束小标
*
*/
private static void merge（int[] a, int s, int m, int t） {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while （i < m && j <= t） {
if （a[i] <= a[j]） {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
while （i < m） {
tmp[k] = a[i];
i++;
k++;
}
while （j <= t） {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy（tmp, 0, a, s, tmp.length）;
}
/**
*
* @param a
* @param s
* @param len
* 每次归并的有序集合的长度
*/
public static void mergeSort（int[] a, int s, int len） {
int size = a.length;
int mid = size / （len << 1）;
int c = size & （（len << 1） - 1）;
// -------归并到只剩一个有序集合的时候结束算法-------//
if （mid == 0）
return;
// ------进行一趟归并排序-------//
for （int i =
升级会员 