1.直接插入排序

经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。

将第一个数和第二个数排列，随后组成一个井然有序编码序列
将第三个数插进进来，组成一个新的井然有序编码序列。
对第四个数、第五个数……直至最终一个数，反复第二步。
要怎么写写出编码：
最先设置插进频次，即循环系统频次，for(inti=1;i设置插进数和获得早已安排好编码序列的最终一个数的十位数。insertNum和j=i-1。
从最终一个数刚开始往前循环系统，假如插进数低于当今数，就将当今数向后挪动一位。
将当今数置放到空着的部位，即j+1

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

public void insertSort(int[] a){
int length=a.length;//数组长度，将这个提取出来是为了提高速度。
int insertNum;//要插入的数
for(int i=1;i<length;i++){//插入的次数
insertNum=a[i];//要插入的数
int j=i-1;//已经排序好的序列元素个数
while(j>=0&&a[j]>insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格
a[j+1]=a[j];//元素移动一格
j–;
}
a[j+1]=insertNum;//将需要插入的数放在要插入的位置。
}
}

2.希尔排序

对于直接插入排序问题，数据量巨大时。

将数的数量设成n，取单数k=n/2，将下标误差为k的书分成一组，组成井然有序编码序列。
再取k=k/2，将下标误差为k的书分成一组，组成井然有序编码序列。
反复第二步，直至k=1实行简易插入排序。
怎样写出编码：
最先明确分的几组。
随后对组里原素开展插入排序。
随后将length/2，反复1,2步，直至length=0才行。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public void sheelSort(int[] a){
int d = a.length;
while (d!=0) {
d=d/2;
for (int x = 0; x < d; x++) {//分的组数
for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始
int j = i - d;//j为有序序列最后一位的位数
int temp = a[i];//要插入的元素
for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。
a[j + d] = a[j];//向后移动d位
}
a[j + d] = temp;
}
}
}
}

3.简单选择排序

常用于取序列中最大最小的几个数时。

(假如每一次较为都互换，那麼就是说互换排列；假如每一次较为完一个循环系统再互换，就是说简单选择排序。)
遍历全部编码序列，将最少的数放到最前边。
遍历剩余的编码序列，将最少的数放到最前边。
反复第二步，直至仅剩一个数。
怎样写出编码：
最先明确循环系统频次，而且记牢当今大数字和位置定位。
将位置定位后边全部的数与当今大数字开展比照，小数赋值给key，并记牢小数的部位。
核对进行后，将最少的值与第一个数的值互换。
反复2、3步。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public void selectSort(int[] a) {
int length = a.length;
for (int i = 0; i < length; i++) {//循环次数
int key = a[i];
int position=i;
for (int j = i + 1; j < length; j++) {//选出最小的值和位置
if (a[j] < key) {
key = a[j];
position = j;
}
}
a[position]=a[i];//交换位置
a[i]=key;
}
}

4.堆排序

对简单选择排序的优化。

将序列构建成大顶堆。
将根节点与最后一个节点交换，然后断开最后一个节点。
重复第一、二步，直到所有节点断开。

代码实现如下：

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

public void heapSort(int[] a){
System.out.println(”开始排序”);
int arrayLength=a.length;
//循环建堆 
for(int i=0;i<arrayLength-1;i++){
//建堆

buildMaxHeap(a,arrayLength-1-i);
//交换堆顶和最后一个元素 
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
private void swap(int[] data, int i, int j) {
// TODO Auto-generated method stub 
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
//对data数组从0到lastIndex建大顶堆 
private void buildMaxHeap(int[] data, int lastIndex) {
// TODO Auto-generated method stub 
//从lastIndex处节点（最后一个节点）的父节点开始 
for(int i=(lastIndex-1)/2;i>=0;i–){
//k保存正在判断的节点 
int k=i;
//如果当前k节点的子节点存在 
while(k*2+1<=lastIndex){
//k节点的左子节点的索引 
int biggerIndex=2*k+1;
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 
if(biggerIndex<lastIndex){
//若果右子节点的值较大 
if(data[biggerIndex]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引 
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值 
if(data[k]<data[biggerIndex]){
//交换他们 
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 
k=biggerIndex;
}else{
break;
}
}
}
}

5.冒泡排序

一般不用。

将编码序列中全部原素两组较为，将较大的放到最终面。
将剩下编码序列中全部原素两组较为，将较大的放到最终面。
反复第二步，直至仅剩一个数。
怎样写出编码：
设定循环系统频次。
设定刚开始较为的十位数，和完毕的十位数。
两组较为，将最少的放进前边去。
反复2、3步，直至循环系统频次结束。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

public void bubbleSort(int[] a){
int length=a.length;
int temp;
for(int i=0;i<a.length;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

6.快速排序

要求时间最快时。

挑选第一个数为p，低于p的数放到左侧，超过p的数放到右侧。
递归的将p左侧和右侧的数都依照第一步开展，直至不可以递归。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void quickSort(int[] numbers, int start, int end) {
if (start < end) {
int base = numbers[start]; // 选定的基准值（第一个数值作为基准值） 
int temp; // 记录临时中间值 
int i = start, j = end;
do {
while ((numbers[i] < base) && (i < end))
i++;
while ((numbers[j] > base) && (j > start))
j–;
if (i <= j) {
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j–;
}
} while (i <= j);
if (start < j)
quickSort(numbers, start, j);
if (end > i)
quickSort(numbers, i, end);
}
}

7.归并排序

速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。

挑选邻近2个数构成一个井然有序编码序列。
挑选邻近的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

public static void mergeSort(int[] numbers, int left, int right) {
int t = 1;// 每组元素个数 
int size = right - left + 1;
while (t < size) {
int s = t;// 本次循环每组元素个数 
t = 2 * s;
int i = left;
while (i + (t - 1) < size) {
merge(numbers, i, i + (s - 1), i + (t - 1));
i += t;
}
if (i + (s - 1) < right)
merge(numbers, i, i + (s - 1), right);
}
}
private static void merge(int[] data, int p, int q, int r) {
int[] B = new int[data.length];
int s = p;
int t = q + 1;
int k = p;
while (s <= q && t <= r) {
if (data[s] <= data[t]) {
B[k] = data[s];
s++;
} else {
B[k] = data[t];
t++;
}
k++;
}
if (s == q + 1)
B[k++] = data[t++];
else
B[k++] = data[s++];
for (int i = p; i <= r; i++)
data[i] = B[i];
}

8.基数排序

用于大量数，很长的数进行排序时。

将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。

本站提供的一切软件、教程和内容信息仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。如果下载的连接失效，请留言更新，本站信息来自网络收集整理，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序和内容，请支持正版，购买注册，得到更好的正版服务。我们非常重视版权问题，如有侵权请邮件与我们联系处理。敬请谅解！

THE END