1 package sort;  2   3 import java.util.ArrayList;  4 import java.util.Random;  5   6 public class Sort  7 {  8   9     public static Random r = new Random(); 10  11     // public static transient ArrayList<String> arr = new 12     // ArrayList<String>();//动态 transient 13     // static int n; 14     // public static int a[] = new int [n];//静态的数组，n也必须要静态的才能行 15  16     // static long l = 88888l; 17     // static float f = 0.12f; 18     //

 19     /** 20      * 堆排序，建立小顶堆。 0-len是待调整的数组，k指向该次被调整子树的根结点 21      */ 22  23     public static void adjustDown(int arr[], int len, int k) 24     { 25         // f = l; 26         int temp = arr[k]; 27  28         for (int i = 2 * k + 1; i <= len; i = 2 * i + 1) 29         { 30             // 只有右孩子存在，且右孩子又是小的结点，那么才会改变探索指针i的方向。（i一直指向待调整子树的孩子结点中值较小的结点，为了小顶堆的目标） 31             if (i < len && arr[i] > arr[i + 1]) 32             { 33                 i++; 34             } 35             if (temp <= arr[i]) 36             { 37                 break; 38             } 39             else 40             { 41                 arr[k] = arr[i]; 42                 k = i;// k一直指向，待调整的子树 的父结点 43             } 44         } 45         arr[k] = temp;// 待调整的k指针没动，直接break出来，没有继续向下调整 46     } 47  48     // 堆排序，先要建立初始堆（从k到0位置，反复向下调整），然后拿出堆顶（对堆的删除），从根破坏了堆性质，又从根往下调整一次即可。 49     // 对堆的插入：新结点放在堆的末端，破坏了最下面子树的堆性质，故向上调整到某一次符合堆的性质即可 50     public static void heapSort(int arr[], int len) 51     { 52         // 这个循环建立了初始堆 53         for (int i = (len - 1) / 2; i >= 0; i--) 54         { 55  56             adjustDown(arr, len, i); 57             // Sort.disArr(arr); 58         } 59         int temp = 0; 60         for (int index = len; index >= 0;) 61         { 62             temp = arr[0]; 63             arr[0] = arr[index]; 64             arr[index] = temp; 65             // System.out.println(arr[index] + " "); 66             // Sort.disArr(arr); 67             index--; 68             adjustDown(arr, index, 0);// 固定从整个树的根开始向下调整 69         } 70  71     } 72  73     // 对小顶堆的插入，插入需要向上调整--AdjustUp 74     public static void insertHeap(int arr[], int k) 75     { 76  77         // k为插入结点的位置 78         int index = k; 79         int temp = arr[index];// n+1指向新放入的元素 80         while ((index - 1) / 2 >= 0 && temp < arr[(index - 1) / 2]) 81         { 82             arr[index] = arr[(index - 1) / 2];// 插入的元素更小，就把父节点值放到子节点中去 83             index = (index - 1) / 2;// 默认父节点值与temp交换了，一直拿temp去和父辈，父辈的父辈……去比较 84             if (index == 0) 85                 break;// 不要在根兜圈圈！减1除2，在0处就不动了；也不能写return ，temp的值还是要赋值回去的 86         } 87         arr[index] = temp; 88     } 89  90     // 利用向上调整，建立初始堆。 91     // 一边不断插入元素，一边自底（k）向上（0）调整一次。 92     public static void heapSort(int arr[]) 93     { 94         // 用直接插入法的思维，一个个点插入堆中，利用向上调整，建立初始堆 95         for (int i = 0; i <= arr.length - 1; i++) 96         { 97             insertHeap(arr, i); 98         } 99 100         // 还是要用到向下调整，输出序列或进行排序，因为只有堆顶元素具有“最”的特性，输出堆顶元素，从顶破坏了堆的结构，自然需要向下调整。101         int temp = 0;102         for (int index = arr.length - 1; index >= 0;)103         {104             temp = arr[0];105             arr[0] = arr[index];106             arr[index] = temp;107             // System.out.println(arr[index] + " ");108             // Sort.disArr(arr);109             index--;110             adjustDown(arr, index, 0);111         }112     }113 114     public static void selectSort(int a[])115     {116         int i = 0, j = 0;117         // int restMin = 0;118         int index = 0;119         int temp = 0;120         // 从第0个位置选定元素到第倒数第二个位置，最后只剩一个元素，就不用选定位置了121         for (i = 0; i < a.length - 1; i++)122         {123             // restMin = a[i];//为找到最值做准备;剩下位置中的最小值124             index = i;// 必须先初始化为当前位置,因为最值可能就是当前位置的元素嘛125             // j指向待比较的元素126             for (j = i + 1; j < a.length; j++)127             {128                 // a[index]值是变化的，用index指向剩下位置中的最小值129                 if (a[j] < a[index])130                 {131                     // restMin = a[j];//restMin保存最小值132                     index = j;// 记录最值的位置，同时a[index]自然也记录了最值的大小133                 }134             }135             // swap 交换最小值和当前位置元素的值136             if (index != i)137             {138                 temp = a[i];139                 a[i] = a[index];140                 a[index] = temp;141             }142 143         }144     }145 146     // 合并段中，把mid位置的放前后和后段，会影响mid取值的计算，以及边界的控制。147     public static void merge(int a[], int left, int mid, int right)148     {149         if (left >= right)150             return;151 152         int index1 = 0;// 游标指向合并中的一段[0 到 mid-left-1]，检测指针153         int index2 = mid - left;// 游标指向合并中的另一段[mid-left- right - left]154         int k = left;// 指向合并后序列的位置,存放指针155 156         // 在a中取原数据， 在b上合并，再把最终结果保存回原来的数组a；或者copy数据到b，把合并后结果直接覆盖到a上157         int b[] = new int[right - left + 1];158 159         for (int i = 0; i < right - left + 1; i++)160         {161             b[i] = a[left + i];162         }163 164         while (index1 <= mid - left - 1 && index2 <= right - left)165         {166             if (b[index1] <= b[index2])167             {168                 a[k++] = b[index1++];169             }170             else171             {172                 a[k++] = b[index2++];173             }174         }175 176         while (index1 <= mid - left - 1)177         {178             a[k++] = b[index1++];// 没有检测完的，复制179         }180         while (index2 <= right - left)181         {182             a[k++] = b[index2++];183         }184     }185 186     public static void mergeSort(int a[], int left, int right)187     {188         if (left >= right)189             return;190         int mid = (left + right) / 2 + 1;191         mergeSort(a, left, mid - 1);192         mergeSort(a, mid, right);193         merge(a, left, mid, right);194 195     }196 197     /**198      * 199      * 交换排序之冒泡排序，结果升序排列200      */201     public static void bubbleSort(int a[])202     {203         int i = 0, j = 0, temp = 0;204         boolean swaped = false;205         for (i = 0; i < a.length; i++)206         {207             swaped = false;208             // 会有j+1，所以注意边界控制209             for (j = 0; j < a.length - i - 1; j++)210             {211                 if (a[j] > a[j + 1])212                 {213                     temp = a[j];214                     a[j] = a[j + 1];215                     a[j + 1] = temp;216                     swaped = true;217                 }218             }219             if (swaped == false)220             {221                 break;222             }223         }224     }225 226     /**227      * 交换排序之快速排序228      */229 230     // public static int partition2(int a[], int left, int right)231     // {232     // // int index = left + r.nextInt(right-left+1);233     // int value = http://www.mamicode.com/a[left];>234     // // System.out.println(left + " -- " + right + " 基准元素是 : a[" +index +235     // // "]=" + a[index]);236     // while (left < right)237     // {238     // // 等于枢轴值的元素在轴的或左边或右边都没有关系，只要保证小于它的在左边，大于它的在右边239     // while (a[left] <= value && left < right)240     // left++;241     //242     // while (a[right] >= value && left < right)243     // right--;244     //245     // if (left < right)246     // {247     // // swap前后两个元素；但是已经不能保证此时的下标值还在枢轴的两侧248     // int temp = a[left];249     // a[left] = a[right];250     // a[right] = temp;251     // left++;252     // right--;253     // }254     // }255     // // a[left] = value;256     // Sort.disArr(a);257     // System.out.println("本次枢轴值的最终位置（轴的位置）是： " + left);258     // return left;259     // }260 261     public static int partition(int a[], int left, int right)262     {263         // 基准元素的选择对于快速排序性能影响较大；index264         int index = left + r.nextInt(right - left + 1);// 随机选基准元素，把它放到a[left]哨兵位置，然后从right开始扫描，才是正确的265         /**266          * a[0]当哨兵，保证了，从后扫描，被调换元素一定再以该基准元素为轴的左侧！没调换，直接略过的元素，也一定是处于轴的右侧。267          * 一定要从最两侧一步步逼近枢轴元素的最终位置268          * 快速排序定位轴的位置，关键就看你是怎么把小于枢轴元素值的放到枢轴左边，大于枢轴元素值的放到枢轴右边269          * ；用腾空一个位置的办法也好，有swap的想法也好270          * ，你的代码是如何具体实现的呢？考虑使用双向链表，设置头指针和尾指针，（拔下结点）在头结点之前插入小的，在尾结点之后插入大的271          */272         // if(index > right || index < left)273         // {274         // System.out.println("ERROR index");275         // }276         // else277         // {278         // System.out.println(left + " -- " + right + " 基准元素是 : a[" +index +279         // "]=" + a[index]);280         // }281         // int index = (left + right) / 2;282         int value = http://www.mamicode.com/a[index];// 用value保存了当前选取的枢轴元素，就可腾空一个位置283 284         // 一定把枢轴元素交换至最左边（放到最左就从right开始检测，最右就应该从left开始检测），使得腾空的位置从最边上向枢轴的真正位置逼近！而不是一开始就从枢轴元素的起始位置开始移动285 286         int temp = a[left];287         a[left] = a[index];288         a[index] = temp;289 290         //291         while (left < right)292         {293             // 比较中带等号，针对重复元素如：4，3，4，检测指针才会移动，不然就死循环了294 295             // 先让右侧开始检测，对于4,9；选了9当value，直接开始right--就不对296             while (left < right && a[right] >= value)297             {298                 right--;299             }300             a[left] = a[right];301             // index = right;302             // if(left < right)303             // {304             // //这样需要比较一次left和right是否重合；与它自己的值和自己比较，指针移动一次；效果上没有改进305             // left++;306             // }307             // left++;//错误。当left与right指针重合时，这句话执行就不对，强制的多加了一次！重合之前都是对的308             while (left < right && a[left] <= value)309             {310                 left++;311             }312             a[right] = a[left];313             // index = left;314             // if(left < right)315             // {316             // //这样需要比较一次left和right是否重合；与它自己的值和自己比较，指针移动一次；效果上没有改进317             // right--;318             // }319         }320         // 必然left==right了321         a[left] = value;322         // System.out.println(" 划分点(该元素最终位置)： " + left);323         return left;324     }325 326     public static void quikSort(int a[], int left, int right)327     {328         if (left >= right)329             return;330         int p = partition(a, left, right);331         quikSort(a, left, p - 1);332         quikSort(a, p + 1, right);333     }334 335     /**336      * 直接插入排序，结果为升序337      * 338      * @param a339      */340     public static void insertSort(int a[])341     {342         int i = 0, j = 0, temp = 0;343         for (i = 2; i <= a.length; i++)344         {345             a[0] = a[i];// a[0]是哨兵346             // i指向带插入的元素，从第二个开始试探，如果比前一个小，就要插入；一定是跟前一个比，而不是a[i]与a[i+1]347             if (a[i] < a[i - 1])348             {349                 // 找到合适的插入位置，j指向已经有序的端;哨兵保证 最多j==1时， 一定会停下来350                 j = i - 1;351                 while (a[j] > a[0])352                 {353                     a[j + 1] = a[j];//后移，数组上实现的直接插入排序就是要大量移动元素，考虑单链表，从头往后比较并插入？例如：最小值就放尾结点，然后依次插入，链表里面就呈降序排列，从大到小链接起来。354                     j--;355                 }356                 a[j + 1] = a[0];357             }358         }359     }360 361     public static void disArr(int a[])362     {363         int i = 0;// java中，定义在for中的int i ，作用域就只在for中364         for (i = 0; i < a.length - 1; i++)365         {366             System.out.print(a[i] + " ");367         }368         System.out.println(a[i]);369     }370 371     public static void main(String[] args)372     {373         int a[] = { 9, 14, 4, 46, 9, 10 };374         // System.out.println(-1 / 2);//负0打印也是0375         Sort.disArr(a);376         // Sort.bubbleSort(a);377         // Sort.quikSort(a, 0, a.length-1);378         // Sort.mergeSort(a, 0, a.length - 1);379         // Sort.selectSort(a);380         // Sort.heapSort(a, a.length - 1);//建立小根堆，把小的放后面，在数组里面便是降序排列了。381         Sort.heapSort(a);// 建立小根堆，把小的放后面，在数组里面便是降序排列了。382         Sort.disArr(a);383         // System.out.println(Integer.toHexString(15));//打印出来还是不会带16进制的0x前缀384         // test(1);385         // test(a[0]);386         // test(Integer.valueOf(3));387         // short i = -3;388         // System.out.println( -3 >>> 1);389         // System.out.println(-0x8000 < 0);390         // System.out.print(Math.pow(2, 15));391     }392 393     // public static void test(int d)394     // {395     //396     // System.out.println("int: " + d);397     // }398     //399     // public static void test(double d)400     // {401     // System.out.println("double: " + d);402     // }403     //404     // public static void test(Integer i)405     // {406     // System.out.println("Integer: " + i.intValue());407     // }408 }