Hey Sort
The shortest way to do many things is to only one thing at a time. – 做许多事情的捷径就是一次只做一件事.
最近有同学问我,什么算法排序比较高效,比较实用,我呢只能说,每个排序都有其优点,都有其劣势,比如:当数据量n小的时候,可以采用插入排序或选择排序,当数据量n大的时候,则应采用时间复杂度为O(nlogn)的排序算法,如快速排序,堆排序,或者合并排序,因此每个排序都有其用处,需要根据自己的需求进行选择合适的排序方法.
接下来就给大家,简单演示下 选择排序与 shell排序的不同
选择排序 执行流程
(1) 首先 从原始数组中选择最小的一个数据,将其和位于第一个位置的数据进行交换.
(2) 接着从剩下的n-1个数据中选择次小的一个元素,将其和第二个位置的数据进行交换.
(3) 然后,这样不断重复,直到最后两个数据完成交换至此,完成了对原始数组的从小到大的排序
详情爱码如下:
private static void SelectSort(int a[]){
int index ,temp;
for (int i = 0;i<a.length-1;i++){
index = i;
for (int j = i+1; j < a.length; j++) {
if(a[j]>a[index]){
index = j;
}
}
if(index!=i){
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
System.out.println("第--" + i + "--步的操作时是:");
for (int h = 0;h<a.length;h++){
System.out.print(" " + a[h]);
}
System.out.println(" ");
}
}
shell算法严格来说基于插入排序的思想,其又称为希尔排序或者缩小增量排序,其排序流程如下:
(1) 将有n个元素的数组分成n/2的数字序列,第1个数据和第n/2+1个数据为一对,...
(2) 一次循环使每一个序列对排好顺序.
(3) 然后再变成n/4个序列,进行排序.
(4) 不断重复以上过程,随着序列减少最后变成一个,也就完成了排序.
爱码如下:
private static void shell(int a[]){
int i,j,h;
int r,temp;
int x = 0 ,len = a.length;
for (r = len/2;r>=1; r/=2) {
for (i = r; i < len;i++) {
temp = a[i];
j = i-r;
while (j>=0&&temp<a[j]){
a[j+r] = a[j];
j-= r;
}
a[j+r] = temp;
}
x++;
System.out.println("第--" + x + "--步的排序结果是");
for (h = 0;h<len;h++){
System.out.print(a[h] + " ");
}
System.out.println(" ");
}
}
为了测试,我特意进行了一次比较,结果证明,shell排序效率,确实略高一丝.测试如下:
public class ShellOperate {
// 生成 80 个数据
private static int num = 80;
// shell 排序
private static void shell(int a[]){
int i,j,h;
int r,temp;
int x = 0 ,len = a.length;
for (r = len/2;r>=1; r/=2) {
for (i = r; i < len;i++) {
temp = a[i];
j = i-r;
while (j>=0&&temp<a[j]){
a[j+r] = a[j];
j-= r;
}
a[j+r] = temp;
}
x++;
System.out.println("第--" + x + "--步的排序结果是");
for (h = 0;h<len;h++){
System.out.print(a[h] + " ");
}
System.out.println(" ");
}
}
// 选择排序
private static void SelectSort(int a[]){
int index ,temp;
for (int i = 0;i<a.length-1;i++){
index = i;
for (int j = i+1; j < a.length; j++) {
if(a[j]>a[index]){
index = j;
}
}
if(index!=i){
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
System.out.println("第--" + i + "--步的操作时是:");
for (int h = 0;h<a.length;h++){
System.out.print(" " + a[h]);
}
System.out.println(" ");
}
}
public static void main(String[] args) {
int a[] = new int[num];
int old[] = new int[a.length];
// 生成原数据
for (int i = 0; i <a.length; i++) {
a[i] = (int)(100+Math.random()*(100+1));
}
System.out.println("shell排序之前的结果是---->>>>");
//
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+"__ ");
}
System.out.println(" ");
// 进行备份
System.arraycopy(a,0 ,old ,0 ,a.length);
// 测试shell时间
long start = System.currentTimeMillis();
shell(a);
System.out.println("shell时间结束》》》》" + (System.currentTimeMillis() - start));
System.out.println("shell排序后的结果是====》》");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "___");
}
System.out.println(" ");
// 对数据进行还原
System.arraycopy(old,0 ,a ,0 ,old.length );
System.out.println("选择排序的开始之前--------");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+"__> ");
}
// 开始 测试
start = System.currentTimeMillis();
SelectSort(a);
System.out.println("选择时间结束》》》》" + (System.currentTimeMillis() - start));
System.out.println("选择排序后的结果是=============");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "___");
}
}
}
结果如下:
shell排序之前的结果是---->>>>
109__ 122__ 146__ 127__ 163__ 175__ 130__ 155__ 197__ 162__ 128__ 113__ 129__ 183__ 189__ 130__ 143__ 116__ 101__ 164__ 166__ 184__ 179__ 139__ 144__ 108__ 139__ 147__ 191__ 199__ 111__ 195__ 111__ 136__ 194__ 133__ 188__ 175__ 152__ 151__ 157__ 195__ 106__ 182__ 156__ 136__ 188__ 171__ 125__ 131__ 119__ 157__ 117__ 109__ 170__ 105__ 120__ 128__ 178__ 130__ 173__ 129__ 129__ 104__ 176__ 168__ 200__ 124__ 145__ 103__ 148__ 174__ 181__ 138__ 141__ 108__ 145__ 174__ 140__ 156__
第--1--步的排序结果是
109 122 106 127 156 136 130 155 125 131 119 113 117 109 170 105 120 116 101 130 166 129 129 104 144 108 139 124 145 103 111 174 111 136 141 108 145 174 140 151 157 195 146 182 163 175 188 171 197 162 128 157 129 183 189 130 143 128 178 164 173 184 179 139 176 168 200 147 191 199 148 195 181 138 194 133 188 175 152 156
第--2--步的排序结果是
109 122 106 104 144 108 130 124 125 103 111 113 111 109 141 105 120 116 101 130 157 129 129 127 156 136 139 147 145 131 119 157 117 136 170 108 143 128 140 151 166 184 146 139 163 168 188 155 191 162 128 174 129 138 189 130 145 174 152 156 173 195 179 182 176 175 200 171 197 199 148 195 181 183 194 133 188 175 178 164
第--3--步的排序结果是
109 113 106 104 141 105 120 116 101 103 111 122 111 109 144 108 130 124 125 130 119 129 117 127 156 108 139 128 140 131 128 157 129 136 163 130 143 147 145 151 148 174 129 138 170 133 145 155 152 156 157 184 146 139 176 136 188 171 178 162 166 195 179 182 189 168 188 174 191 164 173 195 181 183 194 175 200 175 197 199
第--4--步的排序结果是
105 113 106 101 103 108 120 111 104 130 108 122 116 109 131 109 129 117 125 141 111 130 124 127 144 119 139 128 136 151 128 143 129 138 156 130 145 129 139 156 133 157 146 140 162 136 174 147 145 163 148 184 155 152 164 157 188 171 178 170 166 188 174 182 176 168 195 175 183 189 173 195 179 191 194 175 200 181 197 199
第--5--步的排序结果是
103 101 104 108 105 109 106 109 108 111 111 113 116 117 120 119 124 122 125 127 128 128 129 129 129 130 131 130 133 130 136 136 139 138 139 140 144 141 145 143 145 147 146 151 148 152 155 156 156 157 162 157 164 163 166 168 173 170 174 171 174 175 176 175 178 181 179 182 183 184 188 188 194 189 195 191 197 195 200 199
第--6--步的排序结果是
101 103 104 105 106 108 108 109 109 111 111 113 116 117 119 120 122 124 125 127 128 128 129 129 129 130 130 130 131 133 136 136 138 139 139 140 141 143 144 145 145 146 147 148 151 152 155 156 156 157 157 162 163 164 166 168 170 171 173 174 174 175 175 176 178 179 181 182 183 184 188 188 189 191 194 195 195 197 199 200
shell时间结束》》》》 7
shell排序后的结果是====》》
101___103___104___105___106___108___108___109___109___111___111___113___116___117___119___120___122___124___125___127___128___128___129___129___129___130___130___130___131___133___136___136___138___139___139___140___141___143___144___145___145___146___147___148___151___152___155___156___156___157___157___162___163___164___166___168___170___171___173___174___174___175___175___176___178___179___181___182___183___184___188___188___189___191___194___195___195___197___199___200___
选择排序的开始之前--------
109__> 122__> 146__> 127__> 163__> 175__> 130__> 155__> 197__> 162__> 128__> 113__> 129__> 183__> 189__> 130__> 143__> 116__> 101__> 164__> 166__> 184__> 179__> 139__> 144__> 108__> 139__> 147__> 191__> 199__> 111__> 195__> 111__> 136__> 194__> 133__> 188__> 175__> 152__> 151__> 157__> 195__> 106__> 182__> 156__> 136__> 188__> 171__> 125__> 131__> 119__> 157__> 117__> 109__> 170__> 105__> 120__> 128__> 178__> 130__> 173__> 129__> 129__> 104__> 176__> 168__> 200__> 124__> 145__> 103__> 148__> 174__> 181__> 138__> 141__> 108__> 145__> 174__> 140__> 156__> 第--0--步的操作时是:
200 122 146 127 163 175 130 155 197 162 128 113 129 183 189 130 143 116 101 164 166 184 179 139 144 108 139 147 191 199 111 195 111 136 194 133 188 175 152 151 157 195 106 182 156 136 188 171 125 131 119 157 117 109 170 105 120 128 178 130 173 129 129 104 176 168 109 124 145 103 148 174 181 138 141 108 145 174 140 156
第--1--步的操作时是:
200 199 146 127 163 175 130 155 197 162 128 113 129 183 189 130 143 116 101 164 166 184 179 139 144 108 139 147 191 122 111 195 111 136 194 133 188 175 152 151 157 195 106 182 156 136 188 171 125 131 119 157 117 109 170 105 120 128 178 130 173 129 129 104 176 168 109 124 145 103 148 174 181 138 141 108 145 174 140 156
第--2--步的操作时是:
200 199 197 127 163 175 130 155 146 162 128 113 129 183 189 130 143 116 101 164 166 184 179 139 144 108 139 147 191 122 111 195 111 136 194 133 188 175 152 151 157 195 106 182 156 136 188 171 125 131 119 157 117 109 170 105 120 128 178 130 173 129 129 104 176 168 109 124 145 103 148 174 181 138 141 108 145 174 140 156
......
第--77--步的操作时是:
200 199 197 195 195 194 191 189 188 188 184 183 182 181 179 178 176 175 175 174 174 173 171 170 168 166 164 163 162 157 157 156 156 155 152 151 148 147 146 145 145 144 143 141 140 139 139 138 136 136 133 131 130 130 130 129 129 129 128 128 127 125 124 122 120 119 117 116 113 111 111 109 109 108 108 106 105 104 101 103
第--78--步的操作时是:
200 199 197 195 195 194 191 189 188 188 184 183 182 181 179 178 176 175 175 174 174 173 171 170 168 166 164 163 162 157 157 156 156 155 152 151 148 147 146 145 145 144 143 141 140 139 139 138 136 136 133 131 130 130 130 129 129 129 128 128 127 125 124 122 120 119 117 116 113 111 111 109 109 108 108 106 105 104 103 101
选择时间结束》》》》55
选择排序后的结果是=============
200___199___197___195___195___194___191___189___188___188___184___183___182___181___179___178___176___175___175___174___174___173___171___170___168___166___164___163___162___157___157___156___156___155___152___151___148___147___146___145___145___144___143___141___140___139___139___138___136___136___133___131___130___130___130___129___129___129___128___128___127___125___124___122___120___119___117___116___113___111___111___109___109___108___108___106___105___104___103___101___
由此可以看出 shell排序无论是时间上还是步数上,都比选择排序实用些.
