转自

1.插入排序

 

1.1直接插入排序

 

    这是一种最简单，最容易理解的排序方式，其排序思路如下：假设待排序数组为R[0,1,2,i...n-1]，首先将R[0]看作一个有序的子序列（尽管它只有一个数），从R[1]至R[n-1]开始，逐一向该子序列进行插入操作（由小到大排序），那么左半部分的有序子序列将不断增加，而右半部分的待排序列将不断减少，当有序子序列的长度等于原序列时， 排序结束。
   时间复杂度：O(n^2)
   稳定性：稳定

 

    然而，如何找到待插入元素的位置是插入排序的关键，直接插入排序用的就是最“暴力”的逐一查找法：

    暴力算法1：将R[i]与有序子序列所有的元素比较（不移动，只寻找），找到待插入的位置j后，将R[j，i-1]一次性移动到R[j+1，i]，腾出R[j]的位置让R[i]来插入，其中遍历了一次，移动了一次，很是暴力。

    暴力算法2：在算法1的基础上，每次寻找时，若R[i]小于子序列的元素，就与其交换，这样在遍历的同时就完成了移动的动作，优于算法1。

 

    算法1的实现如下，

 

[java] view plain copy

1. //算法1  
2.         public void insertSort1(TestSort[] src){  
3.             TestSort[] r=this.copy(src);  
4.             int len=r.length;  
5.             for(int i=1;i<=len-1;i++){//从第二个数开始插入  
6.                 int location=i;//寻找待插入位置  
7.                 int tmp=r[i].value;//暂存待插入元素  
8.                 for(int j=i-1;j>=0;j--){  
9.                     //j代表有序子序列的最大索引  
10.                     if(!this.compare(r[i],r[j])){  
11.                         //若小于，则继续寻找位置  
12.                         location=j;  
13.                     }  
14.                 }  
15.                   
16.                 if(location!=i){  
17.                 //将R[location...i-1]移动到R[location+1,i],腾出location处的位置  
18.                     for(int k=i;k>location;k--){  
19.                         r[k].value=r[k-1].value;  
20.                     }  
21.                 }  
22.                 r[location].value=tmp;//填充待插入元素  
23.             }  
24.             //输出  
25.             this.print(r);  
26.         }  

算法2的实现如下：

 

[java] view plain copy

1. //算法2，优于算法1  
2.         public void insertSort2(TestSort[] src){  
3.             TestSort[] r=this.copy(src);  
4.             int len=r.length;  
5.             for(int i=1;i<=len-1;i++){//从第二个数开始插入  
6.                 int tmp=r[i].value;//暂存待排序元素  
7.                 int j=i-1;  
8.                 while((j>=0)&&(tmp<r[j].value)){  
9.                       
10.                     r[j+1].value=r[j].value;  
11.                     j--;  
12.                       
13.                 }  
14.                 r[j+1].value=tmp;//填充待插入元素  
15.             }  
16.             //输出  
17.             this.print(r);  
18.         }  

而直接插入排序一般用算法2就行了。

 

1.2折半插入排序

 

    尽管直接插入排序的算法2优于算法1，但它们都比较暴力，因为若子序列的长度为n，则复杂度就为O(n)。假若有一个数我们第一眼就知道它应该插入到最前面，而有序序列又很长，那么这就是最坏的情况（得从后面一个一个找）。为了能快速找到待插入位置，就引入了能快速寻找的折半查找。

    折半插入排序的原理就是：   在直接插入排序排序的基础上，每次寻找插入位置时将有序子序列分解为高半区high， 和低半区low，mid为(low+high)/2,当待排元素key小于（大于）mid时，则它应该插入低半区（高半区），依次循环。

   时间复杂度：O(n^2)
   稳定性：稳定

算法实现：

[java] view plain copy

1. public void halfInsert(TestSort[] src){  
2.             TestSort[] r=this.copy(src);  
3.             int len=r.length;  
4.             int low,high,tmp;  
5.             int mid;  
6.             for(int i=0;i<len;i++){  
7.                 low=0;//low指向子序列的起始位置  
8.                 high=i-1;//high指向末端       
9.                 tmp=r[i].value;//待插入元素  
10.                 //寻找位置  
11.                 while(low<=high){  
12.                     mid=(low+high)/2;  
13.                     if(r[i].value<r[mid].value)//小于mid  
14.                         high=mid-1;  
15.                     else  
16.                         low=mid+1;  
17.                 }  
18.                 //high+1则为待插入位置  
19.                 //将r[high+1...i-1]移动到r[high+2...i],腾出high+1的位置  
20.                 for(int j=i;j>high+1;j--){  
21.                     r[j].value=r[j-1].value;  
22.                 }  
23.                 r[high+1].value=tmp;  
24.             }  
25.             //输出  
26.             this.print(r);  
27.         }  

1.3希尔排序

 

    希尔排序是一种分组插入的排序方式，它首先将待排序R[]序列按照d1=R.length/2的增量进行分组，然后组内的元素进行插入排序，然后以d2=d1/2的增量重复上述操作，直至dn=1（即所有元素都在同一组内）则完成排序。
   时间复杂度：O(logn*logn*n)=O(n*log2n)
   稳定性：不稳定

算法实现：

[java] view plain copy

1. public void shellSort(TestSort[] src){  
2.             TestSort[] r=this.copy(src);  
3.             int len=r.length;  
4.             int d=len/2;  
5.             while(d>=1){  
6.                 //以d为分组的序列进行直接插入排序，  
7.                 for(int i=d;i<len;i=i+d){  
8.                     int tmp=r[i].value;//暂存待排序元素  
9.                     int j=i-d;//有序子序列的最大索引  
10.                     while(j>=0&&tmp<r[j].value){  
11.                             r[j+d].value=r[j].value;  
12.                             j=j-d;  
13.                     }  
14.                     //此时的j+d为待插入位置  
15.                     r[j+d].value=tmp;  
16.                 }  
17.                 d=d/2;//增量递减  
18.             }  
19.             //输出  
20.             this.print(r);  
21.         }  

2.交换排序

 

2.1冒泡排序

 

    冒泡排序是从第一个元素起，比较相邻的两个元素，按由小到大排序，若前一个大于后一个元素，则交换彼此。如此重复n-1趟，每趟都会将该趟最大的元素放置趟尾，好像“冒泡”一样。
   时间复杂度：O(n^2)
   稳定性：稳定

算法实现：

[java] view plain copy

1. public void bubbleSort(TestSort[] src){  
2.             TestSort[] r=this.copy(src);  
3.             int len=r.length;  
4.             for(int i=0;i<len;i++){//len-1趟  
5.                 for(int j=0;j<len-i-1;j++){//每趟交换的次数  
6.                     if(r[j].value>r[j+1].value){  
7.                         this.swap(r[j],r[j+1]);  
8.                     }  
9.                 }         
10.             }  
11.             //输出  
12.             this.print(r);  
13.         }  

2.2快速排序

 

    快速排序是在冒泡排序的基础上改进的：首先选取R[0...n]序列中的R[0]做为关键字，low和high分别指向序列的开始和结束（低半区和高半区），将小于（大于）R[0]的元素从低半区（高半区）交换至高半区（低半区）而中间则插入R[0]，递归对两边子序列也进行上述操作，直至子序列元素的个数为1。
   时间复杂度：将原始序列无限按二分法分解则复杂度为logn,遍历时low--->high则为n，所以O(logn*n)=O(nlogn)
   稳定性：不稳定

算法实现：

[java] view plain copy

1. public void quickSort(TestSort[] src,int lowIndex,int highIndex){  
2.           
3.             if(lowIndex<highIndex){//保证递归时至少有2个元素  
4.                 TestSort[] r=src;  
5.                 int low=lowIndex;  
6.                 int high=highIndex;  
7.               int location;  
8.                 int key=r[low].value;//关键字  
9.                     while(low<high){  
10.                         while(low<high&&r[high].value>=key){    
11.                             high--;  
12.                         }  
13.                         if(low<high){  
14.                             this.swap(r[high],r[low]);  
15.                         }  
16.                         while(low<high&&r[low].value<=key){         
17.                             low++;  
18.                         }  
19.                         if(low<high){  
20.                             this.swap(r[low],r[high]);  
21.                         }  
22.                     }         
23.                 //待插入位置location=low=high  
24.                 location=low;  
25.                 r[location].value=key;  
26.                 quickSort(r,lowIndex,location-1);//低区递归  
27.                 quickSort(r,location+1,highIndex);//高区递归          
28.             }  
29.               
30.     }  

3.选择排序

 

3.1简单选择排序

 

    设待排序列R[0...i...n-1],待排元素为R[i],有序子序列为R[0...i-1],无序子序列为R[i...n-1],则在 R[i...n-1]中寻找最小的元素，并与R[i]交换(相当于补在有序子序列的后边)，直到有序子序列的长度等于原长为止。
   时间复杂度：O(n^2)
   稳定性：不稳定

算法实现：

[java] view plain copy

1. public void simpleChoose(TestSort[] src){  
2.             TestSort[] r=this.copy(src);  
3.             int len=r.length;  
4.             for(int i=0;i<len;i++){  
5.                 int location=i;  
6.                 int min=r[location].value;  
7.                 for(int j=i+1;j<len;j++){  
8.                     if(r[j].value<min){  
9.                         location=j;  
10.                         min=r[j].value;  
11.                       
12.                     }  
13.                 }  
14.                 if(location!=i){  
15.                     //找到了，在location处  
16.                     this.swap(r[location],r[i]);  
17.                 }  
18.                   
19.             }  
20.             //输出  
21.             this.print(r);  
22.         }  

 

所有排序算法实现：

 

[java] view plain copy

1. import java.util.ArrayList;  
2. public class TestSort{  
3.         public static final int SYSMBOL=0XFF;//占位符号  
4.         public int value;//值  
5.         public int index;//索引  
6.   
7.         /* 
8.             原本想利用对象最为带排序元素存些其他信息，最后发现木有必要。。 
9.         */  
10.         public TestSort(int value,int index){  
11.               
12.             this.value=value;  
13.             this.index=index;  
14.         }  
15.         public TestSort(){}  
16.           
17.         //交换  
18.         public void swap(TestSort a,TestSort b){  
19.               
20.             TestSort tmp=new TestSort();  
21.             tmp.value=a.value;  
22.             //tmp.index=a.index;  
23.               
24.             a.value=b.value;  
25.             //a.index=b.index;  
26.               
27.             b.value=tmp.value;  
28.             //b.index=tmp.index;  
29.               
30.           
31.         }  
32.           
33.         //比大小  
34.         public Boolean compare(TestSort a,TestSort b){  
35.             if(a.value>b.value)  
36.                 return true;  
37.                 return false;  
38.         }  
39.           
40.         //输出  
41.         public void print(TestSort[] r){  
42.           
43.             System.out.printf("%s","索引：");  
44.             for(TestSort e : r){  
45.                   
46.                 if(e.value!=TestSort.SYSMBOL){  
47.                     System.out.printf("%s ",e.index<10?"0"+e.index:e.index);  
48.                 }  
49.             }  
50.             System.out.println("\n");  
51.             System.out.printf("%s","数组：");  
52.             for(TestSort e : r){  
53.                 if(e.value!=TestSort.SYSMBOL){  
54.                     System.out.printf("%s ",e.value<10?"0"+e.value:e.value);  
55.                 }  
56.             }  
57.             System.out.println("\n");  
58.         }  
59.           
60.         //复制元素，由于数组为引用类型  
61.         public TestSort[] copy(TestSort[] src){  
62.               ArrayList<TestSort> list=new ArrayList<TestSort>();  
63.                 for (TestSort e : src) {  
64.                     list.add(new TestSort(e.value,e.index));  
65.                 }  
66.                 TestSort[] r=new TestSort[list.size()];  
67.                 return list.toArray(r);  
68.         }  
69.         /********************************1.插入排序***************************************************/  
70.         /* 
71.         ---------------------------------1.1直接插入排序：--------------------------------------------------- 
72.             这是一种最简单，最容易理解的排序方式，其排序思路如下， 
73.         假设待排序数组为R[0,1,2,i...n]，首先将R[0]看作一个有序的 
74.         子序列（尽管它只有一个数），从R[1]至R[n]开始，逐一向该子序列 
75.         进行插入操作（由小到大），那么左半部分的子序列将不断增加，而 
76.         有半部分的待排序列将不断减少，当有序子序列的长度等于原序列时， 
77.         排序结束。 
78.             时间复杂度：O(n^2) 
79.             稳定性：稳定 
80.         */  
81.           
82.         //算法1  
83.         public void insertSort1(TestSort[] src){  
84.             TestSort[] r=this.copy(src);  
85.             int len=r.length;  
86.             for(int i=1;i<=len-1;i++){//从第二个数开始插入  
87.                 int location=i;//寻找待插入位置  
88.                 int tmp=r[i].value;//暂存待插入元素  
89.                 for(int j=i-1;j>=0;j--){  
90.                     //j代表有序子序列的最大索引  
91.                     if(!this.compare(r[i],r[j])){  
92.                         //若小于，则继续寻找位置  
93.                         location=j;  
94.                     }  
95.                 }  
96.                   
97.                 if(location!=i){  
98.                 //将R[location...i-1]移动到R[location+1,i],腾出location处的位置  
99.                     for(int k=i;k>location;k--){  
100.                         r[k].value=r[k-1].value;  
101.                     }  
102.                 }  
103.                 r[location].value=tmp;//填充待插入元素  
104.             }  
105.             //输出  
106.             this.print(r);  
107.         }  
108.           
109.           
110.         //算法2，优于算法1  
111.         public void insertSort2(TestSort[] src){  
112.             TestSort[] r=this.copy(src);  
113.             int len=r.length;  
114.             for(int i=1;i<=len-1;i++){//从第二个数开始插入  
115.                 int tmp=r[i].value;//暂存待排序元素  
116.                 int j=i-1;  
117.                 while((j>=0)&&(tmp<r[j].value)){  
118.                       
119.                     r[j+1].value=r[j].value;  
120.                     j--;  
121.                       
122.                 }  
123.                 r[j+1].value=tmp;//填充待插入元素  
124.             }  
125.             //输出  
126.             this.print(r);  
127.         }  
128.           
129.           
130.         /* 
131.         ---------------------------------1.2折半插入排序：--------------------------------------------------- 
132.                     在简单插入排序中，为了插入到有序子序列中的合适位置，每次不得不遍历所有的子序列，这样其实复杂度很大。 
133.             假若有一个数我们第一眼就知道它应该插入到最前面，而有序序列又很长，那么这就是最坏的情况（得从后面一个一个找）。 
134.             为了快速找到合适的插入位置，可以利用折半查找：在简单排序的基础上，每次寻找插入位置时将有序子序列分解为高半区high， 
135.             和低半区low，mid为(low+high)/2,当待排元素key小于（大于）mid时，则它应该插入低半区（高半区），依次循环，这样复杂度 
136.             一下子就降为logn了，于是，折半插入排序的性能为， 
137.             时间复杂度：O(nlogn) 
138.             稳定性：稳定 
139.         */  
140.         public void halfInsert(TestSort[] src){  
141.             TestSort[] r=this.copy(src);  
142.             int len=r.length;  
143.             int low,high,tmp;  
144.             int mid;  
145.             for(int i=0;i<len;i++){  
146.                 low=0;//low指向子序列的起始位置  
147.                 high=i-1;//high指向末端       
148.                 tmp=r[i].value;//待插入元素  
149.                 //寻找位置  
150.                 while(low<=high){  
151.                     mid=(low+high)/2;  
152.                     if(r[i].value<r[mid].value)//小于mid  
153.                         high=mid-1;  
154.                     else  
155.                         low=mid+1;  
156.                 }  
157.                 //high+1则为待插入位置  
158.                 //将r[high+1...i-1]移动到r[high+2...i],腾出high+1的位置  
159.                 for(int j=i;j>high+1;j--){  
160.                     r[j].value=r[j-1].value;  
161.                 }  
162.                 r[high+1].value=tmp;  
163.             }  
164.             //输出  
165.             this.print(r);  
166.         }  
167.           
168.         /* 
169.         ---------------------------------1.3希尔排序：--------------------------------------------------- 
170.                     希尔排序是一种分组插入的排序方式，它首先将待排序R[]序列按照d1=R.length/2的增量进行分组，然后 
171.             组内的元素进行插入排序，然后以d2=d1/2的增量重复上述操作，直至dn=1（即所有元素都在同一组内）则 
172.             完成排序。 
173.             时间复杂度：O(logn*logn*n)=O(n*log2n) 
174.             稳定性：不稳定 
175.         */  
176.         public void shellSort(TestSort[] src){  
177.             TestSort[] r=this.copy(src);  
178.             int len=r.length;  
179.             int d=len/2;  
180.             while(d>=1){  
181.                 //以d为分组的序列进行直接插入排序，  
182.                 for(int i=d;i<len;i=i+d){  
183.                     int tmp=r[i].value;//暂存待排序元素  
184.                     int j=i-d;//有序子序列的最大索引  
185.                     while(j>=0&&tmp<r[j].value){  
186.                             r[j+d].value=r[j].value;  
187.                             j=j-d;  
188.                     }  
189.                     //此时的j+d为待插入位置  
190.                     r[j+d].value=tmp;  
191.                 }  
192.                 d=d/2;//增量递减  
193.             }  
194.             //输出  
195.             this.print(r);  
196.         }  
197.         /********************************2.交换排序***************************************************/  
198.         /* 
199.         ---------------------------------2.1冒泡排序：--------------------------------------------------- 
200.                     冒泡排序是从第一元素起，比较相邻的两个元素，按由小到大排序，若前一个大于后一个元素，则交换彼此。 
201.             如此重复n-1趟，每趟都会将该趟最大的元素放置趟尾，好像“冒泡”一样。 
202.             时间复杂度：O(n^2) 
203.             稳定性：稳定 
204.         */  
205.         public void bubbleSort(TestSort[] src){  
206.             TestSort[] r=this.copy(src);  
207.             int len=r.length;  
208.             for(int i=0;i<len;i++){//len-1趟  
209.                 for(int j=0;j<len-i-1;j++){//每趟交换的次数  
210.                     if(r[j].value>r[j+1].value){  
211.                         this.swap(r[j],r[j+1]);  
212.                     }  
213.                 }         
214.             }  
215.             //输出  
216.             this.print(r);  
217.         }  
218.           
219.         /* 
220.         ---------------------------------2.2快速排序：--------------------------------------------------- 
221.                     快速排序是在冒泡排序的基础上改进的：首先选取R[0...n]序列中的R[0]做为关键字，low和high分别指向 
222.             序列的开始和结束（低半区和高半区），将小于（大于）R[0]的元素从低半区（高半区）交换至高半区（低半区） 
223.             而中间则插入R[0]，递归对两边子序列也进行上述操作，直至子序列的个数为1 
224.             时间复杂度：将原始序列无限按二分法分解则复杂度为logn,遍历时low--->high则为n 
225.                                     所以O(logn*n)=O(nlogn) 
226.             稳定性：不稳定 
227.         */  
228.         public void quickSort(TestSort[] src,int lowIndex,int highIndex){  
229.               
230.                 if(lowIndex<highIndex){//保证递归时至少有2个元素  
231.                     TestSort[] r=src;  
232.                     int low=lowIndex;  
233.                     int high=highIndex;  
234.                   int location;  
235.                     int key=r[low].value;//关键字  
236.                         while(low<high){  
237.                             while(low<high&&r[high].value>=key){    
238.                                 high--;  
239.                             }  
240.                             if(low<high){  
241.                                 this.swap(r[high],r[low]);  
242.                             }  
243.                             while(low<high&&r[low].value<=key){         
244.                                 low++;  
245.                             }  
246.                             if(low<high){  
247.                                 this.swap(r[low],r[high]);  
248.                             }  
249.                         }         
250.                     //待插入位置location=low=high  
251.                     location=low;  
252.                     r[location].value=key;  
253.                     quickSort(r,lowIndex,location-1);//低区递归  
254.                     quickSort(r,location+1,highIndex);//高区递归          
255.                 }  
256.                   
257.         }  
258.           
259.         /********************************3.选择排序***************************************************/  
260.         /* 
261.         ---------------------------------3.1简单选择排序：--------------------------------------------------- 
262.                     设待排序列R[0...i...n-1],待排元素为R[i],有序子序列为R[0...i-1],无序子序列为R[i...n-1],则在 
263.             R[i...n-1]中寻找最小的元素，并与R[i]交换(相当于补在有序子序列的后边)，直到有序子序列的长度等于原长为止。 
264.             时间复杂度：O(n^2) 
265.             稳定性：不稳定 
266.         */  
267.         public void simpleChoose(TestSort[] src){  
268.             TestSort[] r=this.copy(src);  
269.             int len=r.length;  
270.             for(int i=0;i<len;i++){  
271.                 int location=i;  
272.                 int min=r[location].value;  
273.                 for(int j=i+1;j<len;j++){  
274.                     if(r[j].value<min){  
275.                         location=j;  
276.                         min=r[j].value;  
277.                       
278.                     }  
279.                 }  
280.                 if(location!=i){  
281.                     //找到了，在location处  
282.                     this.swap(r[location],r[i]);  
283.                 }  
284.                   
285.             }  
286.             //输出  
287.             this.print(r);  
288.         }  
289.           
290.         public static void main(String[] args){  
291.             TestSort obj=new TestSort();  
292.             TestSort[] r=new TestSort[]{  
293.                 new TestSort(10,0),  
294.                 new TestSort(1,1),  
295.                 new TestSort(9,2),  
296.                 new TestSort(2,3),  
297.                 new TestSort(8,4),  
298.                 new TestSort(3,5),  
299.                 new TestSort(7,6),  
300.                 };  
301.                 System.out.println("原始数组：");  
302.                 obj.print(r);  
303.                   
304.                 System.out.println("直接插入算法1：");  
305.                 obj.insertSort1(r);  
306.                   
307.                 System.out.println("直接插入算法2：");  
308.                 obj.insertSort2(r);  
309.                   
310.                 System.out.println("折半插入算法：");  
311.                 obj.halfInsert(r);  
312.                   
313.                 System.out.println("希尔排序算法：");  
314.                 obj.shellSort(r);  
315.                   
316.                 System.out.println("冒泡算法：");  
317.                 obj.bubbleSort(r);  
318.                   
319.                 System.out.println("快速排序：");  
320.                 obj.quickSort(r,0,r.length-1);  
321.                 obj.print(r);  
322.                   
323.                 System.out.println("简单选择数组：");  
324.                 obj.simpleChoose(r);  
325.                 
326.                   
327.                   
328.         }  
329.     }  

结果：