排序算法

1. 冒泡排序

1. 原理

临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子例子为从小到大排序。

2. 代码

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
package com.vgbh;

public class BubbleSorting {

private static int n = 10;//数组长度
private static int[] arr = new int[n];//数组

private static int count = 0;//执行次数

static PublicOut pc= null;//定义外部对象

public static void main(String[] args){
pc = new PublicOut();
pc.data(arr, n);

BubbleSorting bs = new BubbleSorting();
bs.bubble(arr);
}

/*
* 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
* 这样一趟过去后,最大或最小的数字被交换到了最后一位,
* 然后再从头开始进行两两比较交换,直到倒数第二位时结束,
* 其余类似看例子例子为从小到大排序,
*/

public void bubble(int[] arr){
System.out.println("冒泡排序之后:");
for(int x=0;x<n;++x){
for (int y=0;y<n;++y) {
if(y+1 == arr.length) break;
if(arr[y] > arr[y+1]) {
pc.change(arr,y,y+1);//数据转换
count++;
//pc.prin(arr,n);
//System.out.println("zzzzzzz"+arr[x] +" " +arr[x+1]); 测试代码
}
}
}
pc.prin(arr,n);
System.out.println("共执行"+ count +"次");
}
}

3. 后记

哇,现在看见纪念写的代码,我不知道那时候咋写的。。。。。。。

2. 快速排序

1. 原理

快速排序是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

  1. 在数据集之中,选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。 这个操作称为分区 (partition)操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

2. 代码

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
package com.vgbh;

public class QuickSorting {

/*
* 快速排序是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
*
* 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
*
* 利用分治法可将快速排序的分为三步: 在数据集之中,选择一个元素作为”基准”(pivot)。
* 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。 这个操作称为分区 (partition)
* 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
* 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
*/

private static int n = 10;//数组长度
private static int[] arr = new int[10];//数组

static PublicOut pc = null;//外部对象

public static void main(String[] args) {
pc = new PublicOut();

System.out.println("排序前:");
pc.data(arr, n);
pc.prin(arr, n);

QuickSorting qs = new QuickSorting();
qs.quick(arr, 0,9);

System.out.println("排序后:");
pc.prin(arr, n);

}

public void quick (int[] arr,int left,int right) {
if (arr.length > 0) {
if (left < right) {
int pivotpos = partition(arr,left,right);
quick(arr,left,pivotpos-1);
quick(arr,pivotpos+1,right);
}
}

}

public int partition (int[] arr,int left,int right) {
//返回最后定位基准的下标

int temp = arr[left];
while (left < right) {
while (left<right && arr[right]>=temp) {
--right;
//System.out.println("右移一次");
}
arr[left] = arr[right];
//System.out.println("右边的支付给左边");
while (left<right && arr[left]<=temp) {
++left;
//System.out.println("左移一次");
}
arr[right] = arr[left];
//System.out.println("左边的值赋给右边");
}
arr[left] = temp;
//System.out.println(left);
//pc.prin(arr, n);

return left;

/* 一次错误的示范
int pivot = arr[l];
while (l < r) {
while (l<r && arr[l]<=pivot) {
r--;
if (l<r) {
arr[l] = arr[r];
}
}
while (l<r && arr[r]>=pivot) {
l++;
if (l<r) {
arr[r] = arr[l];
}
}
}
arr[l] = pivot;
return l;
*/
}

/*
对于1~10的有规律排序,快速排序可以进行排序。
但对于不规则排序会死循环,会一直在赋值之间来回赋值,从而进入死循环。
*/

3. 后记

这又发现了一个原来的坑,还没有填。。。。。

3. 选择排序

1. 原理

  1. 从n个元素中找出关键字最小的元素与第一个元素交换;
  2. 在从第二个元素开始的n-1个元素中再选出关键字最小的元素与第二个元素交换;
  3. 第k趟,则从第k个元素开始的n-k+1个元素中选出关键字最小的元素与第k个元素交换,直到整个序列按关键字有序。选择排序是不稳定的排序方法。

2. 代码

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
package com.vgbh;

public class SelectSorting {

private static int n = 10 ;//数组长度
private static int[] arr = new int[n] ;//数组

static PublicOut pc = null ;//定义外部对象

public static void main(String args[]) {
pc = new PublicOut();
pc.data(arr,n);
pc.prin(arr,n);

SelectSorting ss = new SelectSorting();
ss.selectOrder(arr);
pc.prin(arr, n);
}

public void selectOrder (int arr[]) {
int min ;
for (int x=0;x<arr.length-1;x++) {
min = x;
for (int y=x+1;y<arr.length;y++) {
if (arr[y] < arr[min]) min = y ;
if (min != x) pc.change(arr, min, x);
}
}
}
}

4. 希尔排序

1. 原理

  1. 将无序数组分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行插入排序;
  2. 然后再选择一个更小的增量,再将数组分割为多个子序列进行排序……最后选择增量为1,即使用直接插入排序,使最终数组成为有序。

增量的选择:选用Knuth间隔序列

2. 代码

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
package com.vgbh;

public class ShellSorting {
private static int n = 10 ;//数组长度
private static int[] arr = new int[n] ;//数组
static PublicOut pc = null ;//定义外部对象
static ShellSorting ss = null ;//定义内部对象

public static void main(String[] args) {
pc = new PublicOut();
ss = new ShellSorting();

ss.data(arr,n);//创建数据
System.out.println("希尔排序前:");
pc.prin(arr, n);//打印数据
ss.shell(arr,n);//希尔排序
System.out.println("希尔排序后:");
pc.prin(arr, n);//打印数据
}

//希尔排序
public void shell (int[] arr,int n) {
int inner , outer ;
int temp ;
int h = 1 ;
while (h < n) h = h*3 + 1;//(Knuth间隔序列:1,4,13,40,121,...)

//System.out.println("\nstart shell sorting:");
while (h > 0) {
//System.out.println("\n\n\n当前的h值为:" + h);
for (outer=h;outer<n;outer++) {
//System.out.println("\n第" + outer + "次循环。");
temp = arr[outer];
inner = outer ;
//System.out.println("--------temp:" + temp + "---------inner:" + inner);

while (inner>h-1 && arr[inner-h]>=temp) {
arr[inner] = arr[inner-h];
inner -= h;
//System.out.println(" arr[inner] :" + arr[inner] + " inner:" + inner);
}
arr[inner] = temp;

//System.out.println("++++++arr[inner]:" + arr[inner]);
}
h = (h-1) / 3;
//pc.prin(arr, n);
}

//System.out.println("end shell sorting:\n");
}

public void data (int[] arr,int n) {//排序的数据
for (int i=0;i<n;i++) {
arr[i] = 10 - i;//按照一定顺序产生数据:10~0
//arr[i] = (int)(Math.random()*10);//随机产生数据:0~10随机
}
}
}

3. 运行过程

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
/*    
此为数据为{10,9,8,7,6,5,4,3,2,1}时的排序结果,可按照程序的运行结果理解程序的步骤。

希尔排序前:
10 9 8 7 6 5 4 3 2 1
---------------

start shell sorting:

当前的h值为:13

10 9 8 7 6 5 4 3 2 1
---------------


当前的h值为:4

第4次循环。
--------temp:6---------inner:4
arr[inner] :10 inner:0
++++++arr[inner]:6

第5次循环。
--------temp:5---------inner:5
arr[inner] :9 inner:1
++++++arr[inner]:5

第6次循环。
--------temp:4---------inner:6
arr[inner] :8 inner:2
++++++arr[inner]:4

第7次循环。
--------temp:3---------inner:7
arr[inner] :7 inner:3
++++++arr[inner]:3

第8次循环。
--------temp:2---------inner:8
arr[inner] :10 inner:4
arr[inner] :6 inner:0
++++++arr[inner]:2

第9次循环。
--------temp:1---------inner:9
arr[inner] :9 inner:5
arr[inner] :5 inner:1
++++++arr[inner]:1

2 1 4 3 6 5 8 7 10 9
---------------

当前的h值为:1

第1次循环。
--------temp:1---------inner:1
arr[inner] :2 inner:0
++++++arr[inner]:1

第2次循环。
--------temp:4---------inner:2
++++++arr[inner]:4

第3次循环。
--------temp:3---------inner:3
arr[inner] :4 inner:2
++++++arr[inner]:3

第4次循环。
--------temp:6---------inner:4
++++++arr[inner]:6

第5次循环。
--------temp:5---------inner:5
arr[inner] :6 inner:4
++++++arr[inner]:5

第6次循环。
--------temp:8---------inner:6
++++++arr[inner]:8

第7次循环。
--------temp:7---------inner:7
arr[inner] :8 inner:6
++++++arr[inner]:7

第8次循环。
--------temp:10---------inner:8
++++++arr[inner]:10

第9次循环。
--------temp:9---------inner:9
arr[inner] :10 inner:8
++++++arr[inner]:9

1 2 3 4 5 6 7 8 9 10
---------------


end shell sorting:

希尔排序后:
1 2 3 4 5 6 7 8 9 10
---------------

*/

4. 后记

对于希尔排序,我还是建议动手在纸上演算,其实会出现很多错误,但也会更深刻的理解希尔排序,动手丰衣足食。

5. 堆排序

1. 原理

堆排序算法思想: 堆排序,顾名思义,就是基于堆。

因此先来介绍一下堆的概念:
堆分为最大堆和最小堆,其实就是:完全二叉树或近似完全二叉树。

二叉树的特点:

  1. 最大堆要求节点的元素都要大于其孩子。
  2. 最小堆要求节点元素都小于其左右孩子。

有了上面的定义,我们可以得知,处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最大堆,依次类推,最终得到排序的序列。

本质上讲,堆排序是一种选择排序,每次都选择堆中最大的元素进行排序。只不过堆排序选择元素的方法更为先进,时间复杂度更低,效率更高。

步骤:

  1. 首先从第一个非叶子节点开始,比较当前节点和其孩子节点,将最大的元素放在当前节点,交换当前节点和最大节点元素。
  2. 将当前元素前面所有的元素都进行1的过程,这样就生成了最大堆
  3. 将堆顶元素和最后一个元素交换,列表长度减1。由此无序区减1,有序区加1
  4. 剩余元素重新调整建堆
  5. 继续3和4,直到所有元素都完成排序

时间复杂度:
堆排序的平均时间复杂度为O(nlogn),接近于最坏的时间复杂度。在最好情况下,时间复杂度为O(1).

算法总结:
堆排序时间复杂度:O(nlogn)。堆排序对原始记录的排序状态并不敏感,其在性能上要远远好过于冒泡、简单选择、直接插入排序。

2. 代码

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
package com.vgbh;

/*
* 堆排序
*/
public class heapSorting {

private static int n = 10 ;//数组长度
private static int[] arr = new int[n] ;//数组

static PublicOut pc = null ;//定义外部对象

public static int count = 0;//运行次数

public static void main(String[] args) {

pc = new PublicOut();
pc.data(arr, n);
pc.prin(arr, n);

heapSorting hs = new heapSorting();
hs.heap(arr);

pc.prin(arr, n);

//System.out.println("最后共运行" + count + "次。");

}

//数据结构的p281有详细的运算过程 详解:http://www.ixywy.com/zsjz/2564.html

//堆排序
public void heap (int[] arr) {
//将数组转化为大堆
for (int i=arr.length / 2; i>=0; i--) {
buildHeap(arr,i,arr.length);
}

//将最小值与最大值交换,并调整二叉树
for (int i=arr.length - 1; i>0; i--) {
swap(arr, 0, i);//将父元素和当前未经排序子序列的最后一个记录交换
buildHeap(arr, 0, i);//交换之后,重新比对二叉树,不符合则要调整。
}

}

/*
* 创建堆
* arr:数组
* x:需要构建堆的根节点的序号
* y:数组长度
*/
public void buildHeap (int[] arr,int x,int y) {
count++;
int child ;
int father ;
for (father = arr[x]; leftChild(x) < y; x = child) {
child = leftChild(x);

//如果左子树小于右子树,则需要比较右子树和父节点
if (child != y-1 && arr[child] < arr[child+1]) {
child++;//自增可以指向父节点
}

//如果父节点小于孩子节点,则需要交换
if (father < arr[child]) {
arr[x] = arr[child];
} else {
break;//大堆未被破坏,不需要调整
}
}
arr[x] = father;
}

//交换元素
public void swap (int[] arr,int x,int y) {
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}

//获取左孩子结点
public int leftChild (int i) {
return 2 * i + 1;
}
}

3. 后记

堆排序,我想了好几天,最后还是参考了一下别人的博客,看了许多的解释,不过还是下面这些最好理解:
http://www.ixywy.com/zsjz/2564.html
http://blog.csdn.net/zdp072/article/details/44227317

6. 归并排序

1. 原理

两路归并排序算法思路:

  1. 把 n个记录看成 n个长度为1的有序子表;
  2. 进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表;
  3. 重复第2步直到所有记录归并成一个长度为 n的有序表为止。

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法步骤:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

2. 代码

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
package com.vgbh;

/*
* 归并排序
*/
public class MergeSorting {

private static int n = 10 ;//数组长度
private static int[] arr = new int[n] ;//数组

static PublicOut pc = null ;//定义外部对象
public static int count = 0;//运行次数

public static void main(String[] args) {
pc = new PublicOut();
pc.data(arr, n);
System.out.println("排序前:");
pc.prin(arr, n);

MergeSorting ms = new MergeSorting();
ms.merge(arr, n);

System.out.println("排序后:");
pc.prin(arr, n);

System.out.println("最后共运行" + count + "次。");

}

public void merge (int arr[],int n) {
int[] temp = new int[n];
mergeSort(arr,0,n-1,temp);
}

/*
* 归并排序,使用递归
*/
public void mergeSort (int arr[],int first,int last,int temp[]) {
if (first < last) {
int bin = (first + last) / 2;
mergeSort(arr,first,bin,temp);//左边
mergeSort(arr,bin+1,last,temp);//右边
mergeArray(arr,first,bin,last,temp);//数组排序
}
}

/*
* 合并数组
* 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。
* 然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可
*/
public void mergeArray (int arr[],int first,int bin,int last,int temp[]) {
int i = first;//第一个数组的开始位
int m = bin;//第一个数组的末尾值
int j = bin + 1;//第二个数组的开始位
int n = last;//第二个数组的末尾值
int k = 0;//替补数组长度值

//System.out.println("开始合并数组: i ,m ,j , n , k " + i + m + j + n + k);

//将数组分割为两部分,两部分进行比较,进行排序,排序后放在替补数组中,最终将排序好的数组返回到原数组。
//再比对过程中,会首先将某个分数组中的值比对完后,在进行全部赋值操作。(注意观察赋值完成后i和j的值)
while (i<=m && j<=n) {
if (arr[i] <= arr[j]) {
//temp[k] = arr[i]; k++; i++;
temp[k++] = arr[i++];
//System.out.println("temp[k] " + temp[k-1] + " k " + (k-1) + " i " + i + "这里是i");
count++;
} else {
//temp[k] = arr[j]; k++; j++;
temp[k++] = arr[j++];
//System.out.println("temp[k] " + temp[k-1] + " k " + (k-1) + " j " + j + "这里是j");
count++;
}
}

while (j <= n) {//补偿未排序进数组的数
//temp[k] = arr[j]; k++; j++;
temp[k++] = arr[j++];
//System.out.println("temp[k]" + temp[k-1] + " k" + (k-1) + " j" + j);
count++;
}

while (i <= m) {//补偿未排序进数组的数
//temp[k] = arr[i]; k++; i++;
temp[k++] = arr[i++];
//System.out.println("temp[k] " + temp[k-1] + " k " + (k-1) + " i " + i);
count++;
}

for (int x=0;x<k;x++) {
arr[first+x] = temp[x];
//System.out.println(temp[x] + " 最后的交换值 temp[x]");
}
}
}

3. 后记

注释的部分都是测试代码,可以更好地帮助你理解整个运行过程。