几种排序实现代码
package com.delicacy.oatmeal.test.suanfa.sort;import java.util.Arrays;import java.util.Random;public class ArraySort {public static void main(String[] args) {int[] arr = getInts();System.out.println("selectSort");long a = System.nanoTime();selectSort(arr);long b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("bubbleSort");a = System.nanoTime();bubbleSort(arr);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("quickSort");a = System.nanoTime();quickSort(arr, 0, arr.length - 1);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("insertSort");a = System.nanoTime();insertSort(arr);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("Arrays.sort");a = System.nanoTime();Arrays.sort(arr);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("shellSort");a = System.nanoTime();shellSort(arr);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("mergeSort");a = System.nanoTime();mergeSort(arr,0,arr.length-1);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("heapSort");a = System.nanoTime();heapSort(arr);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);arr = getInts();System.out.println("radixSort");a = System.nanoTime();radixSort(arr, 5);b = System.nanoTime();System.out.println(Arrays.toString(arr));System.out.println(b - a);}private static int[] getInts() {Random r = new Random();int[] arr = new int[100];for (int i = 0; i < arr.length; i++) {arr[i] = r.nextInt(10000);}return arr;}/*** 选择排序<br/>* <li>在未排序序列中找到最小元素，存放到排序序列的起始位置</li>* <li>再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。</li>* <li>以此类推，直到所有元素均排序完毕。</li>** @param numbers*/public static void selectSort(int[] numbers) {int tmp,size = numbers.length;for (int i = 0; i < size; i++) {int k = i;for (int j = size-1; j>i; j--) {if (numbers[j] > numbers[k]) k = j;}swap(numbers, i, k);}}private static void swap(int[] numbers, int i, int k) {int tmp;tmp = numbers[i];numbers[i] = numbers[k];numbers[k] = tmp;}/*** 冒泡法排序<br/>* <p>* <li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li>* <li>对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li>* <li>针对所有的元素重复以上的步骤，除了最后一个。</li>* <li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li>** @param numbers 需要排序的整型数组*/public static void bubbleSort(int[] numbers) {int tmp,size = numbers.length;for (int i = 0; i < size - 1; i++) {for (int j = i+1; j < size; j++) {if (numbers[i]>numbers[j]){swap(numbers,i,j);}}}}/*** 快速排序<br/>* <ul>* <li>从数列中挑出一个元素，称为“基准”</li>* <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）* 。在这个分割之后， 该基准是它的最后位置。这个称为分割（partition）操作。</li>* <li>递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>* </ul>** @param numbers* @param start* @param end*/public static void quickSort(int[] numbers, int start, int end) {if(end <= start)return;int tmp = numbers[start];int i = start,j = end;while (i<j){while (i<j&&numbers[j]>=tmp)j--;while (i<j&&numbers[i]<=tmp)i++;if(i<j){swap(numbers,i,j);}}numbers[start] = numbers[i];numbers[i] = tmp;quickSort(numbers,start,i-1);quickSort(numbers,i+1,end);}/*** 插入排序* <p>* 从第一个元素开始，该元素可以认为已经被排序* 取出下一个元素，在已经排序的元素序列中从后向前扫描* 如果该元素（已排序）大于新元素，将该元素移到下一位置* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置* 将新元素插入到该位置中* 重复步骤2** @param numbers*/public static void insertSort(int[] numbers) {int size = numbers.length,j,tmp;for (int i = 0; i < size; i++) {tmp = numbers[i];for (j = i; 0 < j && numbers[j-1] <tmp ; j--) {numbers[j] = numbers[j-1];}numbers[j] = tmp;}}/*** 归并排序* <p>* 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列* 设定两个指针，最初位置分别为两个已经排序序列的起始位置* 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置* 重复步骤3直到某一指针达到序列尾* 将另一序列剩下的所有元素直接复制到合并序列尾**/public static void mergeSort(int a[],int start,int end){if(a!=null&& end>start){int mid = (end+start)/2;mergeSort(a,start,mid);mergeSort(a,mid+1,end);merge(a,start,mid,end);}}private static void merge(int a[], int start, int mid, int end){int arr[] = new int[end-start+1];int i =start,j=mid+1,k=0;while (i<=mid && j<=end){if (a[i]<=a[j])arr[k++] = a[i++];elsearr[k++] = a[j++];}while (i<=mid)arr[k++] = a[i++];while (j<=end)arr[k++] = a[j++];for (i = 0; i < k; i++) {a[start+i] = arr[i];}}/*** 希尔排序算法* 基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列* 中的记录“基本有序”时，再对全体记录进行依次直接插入排序** @param a*/public static void shellSort(int[] a) {int dk = a.length / 2;while (dk >= 1) {ShellInsertSort(a, dk);dk = dk / 2;}}private static void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了for (int i = dk; i < a.length; i++) {int i1 = a[i]; // 为待插入元素int i2 = a[i - dk];if (i1 < i2) { // 前面的大于后面的int j;for (j = i - dk; j >= 0 && i1 < a[j]; j = j - dk) {//通过循环，逐个后移一位找到要插入的位置。a[j + dk] = a[j];}a[j + dk] = i1;//插入}}}/*** 堆排序* @param nums 待排序数组序列* @return 排好序的数组序列*/public static int[] heapSort(int[] nums) {for (int i = nums.length / 2 - 1; i >= 0; i--) {heapAdjust(nums, i, nums.length);}for (int i = nums.length - 1; i > 0; i--) {int temp = nums[i];nums[i] = nums[0];nums[0] = temp;heapAdjust(nums, 0, i);}return nums;}/*** 调整堆** @param nums 待排序序列* @param parent 待调整根节点* @param length 数组序列长度*/private static void heapAdjust(int[] nums, int parent, int length) {int temp = nums[parent];int childIndex = 2 * parent + 1; //完全二叉树节点i从编号1开始的左子节点位置在2i，此处数组下标从0开始，即左子节点所在数组索引位置为：2i + 1while (childIndex < length) {if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {childIndex++; //节点有右子节点，且右子节点大于左子节点，则选取右子节点}if (temp > nums[childIndex]) {break; //如果选中节点大于其子节点，直接返回}nums[parent] = nums[childIndex];parent = childIndex;childIndex = 2 * parent + 1; //继续向下调整}nums[parent] = temp;}//arr是要排序的数组，max是数组中最大的数有几位public static void radixSort(int[] arr, int max) {//count数组用来计数int[] count = new int[arr.length];//bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据int[] bucket = new int[arr.length];//k表示第几位，1代表个位，2代表十位，3代表百位for (int k = 1; k <= max; k++) {//把count置空，防止上次循环的数据影响for (int i = 0; i < arr.length; i++) {count[i] = 0;}//分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量//以下便称为桶//即此循环用来统计每个桶中的数据的数量for (int i = 0; i < arr.length; i++) {count[getFigure(arr[i], k)]++;}//利用count[i]来确定放置数据的位置for (int i = 1; i < arr.length; i++) {count[i] += count[i - 1];}//执行完此循环之后的count[i]就是第i个桶右边界的位置//利用循环把数据装入各个桶中，注意是从后往前装//这里是重点，一定要仔细理解for (int i = arr.length - 1; i >= 0; i--) {int j = getFigure(arr[i], k);bucket[count[j] - 1] = arr[i];count[j]--;}//将桶中的数据取出来，赋值给arrfor (int i = 0; i < arr.length; i++) {arr[i] = bucket[i];}}}static int getFigure(int num, int k) {if (k < 1) throw new IllegalArgumentException("k should not be less than 1");return (num / pow(10,k-1)) % 10;}static int pow(int x, int y) {if (y < 0) throw new IllegalArgumentException("y should not be less than 0");int tmp = 1;for (int i = 0; i < y; i++) {tmp *= x;}return tmp;}}
selectSort[9933, 9918, 9914, 9821, 9673, 9605, 9506, 9471, 9446, 9437, 9424, 9364, 9314, 9202, 9194, 8931, 8782, 8753, 8652, 8624, 8546, 8416, 8256, 8196, 8163, 8151, 8098, 7987, 7907, 7887, 7873, 7862, 7840, 7566, 7201, 6969, 6901, 6648, 6555, 6385, 6335, 6315, 6266, 6263, 6225, 6127, 6071, 6054, 5992, 5684, 5647, 5599, 5558, 5537, 5510, 5473, 5125, 5010, 4985, 4954, 4565, 4340, 4278, 4245, 4193, 4100, 3917, 3842, 3544, 3267, 3190, 3017, 2835, 2781, 2685, 2547, 2544, 2397, 2389, 2213, 2130, 2071, 2068, 1908, 1863, 1842, 1789, 1787, 1533, 1360, 971, 808, 750, 743, 736, 718, 668, 419, 308, 235]333432bubbleSort[9685, 9587, 9540, 9117, 9110, 9057, 9004, 8840, 8805, 8669, 8516, 8484, 8463, 8396, 8281, 8225, 8222, 7986, 7906, 7806, 7759, 7605, 7491, 7489, 7475, 6941, 6805, 6694, 6639, 6629, 6479, 6472, 6448, 6309, 6275, 6231, 6230, 6150, 6103, 6080, 6078, 5893, 5798, 5712, 5646, 5615, 5608, 5355, 5306, 5258, 5217, 5053, 4743, 4691, 4666, 4622, 4621, 4443, 4357, 4313, 3942, 3862, 3796, 3703, 3547, 3511, 3480, 3440, 3397, 3220, 3017, 2997, 2995, 2935, 2879, 2788, 2768, 2674, 2521, 2420, 2301, 2223, 2174, 2025, 1862, 1858, 1838, 1709, 1555, 1549, 1387, 1039, 1021, 850, 742, 610, 526, 424, 249, 233]519505quickSort[152, 220, 222, 254, 329, 474, 504, 982, 984, 1063, 1324, 1343, 1362, 1386, 1426, 1509, 1637, 1773, 1803, 1841, 1843, 2045, 2082, 2290, 2566, 2689, 2699, 2788, 2940, 3002, 3080, 3087, 3199, 3392, 3474, 3622, 3758, 4066, 4142, 4167, 4225, 4319, 4644, 4997, 5148, 5152, 5278, 5413, 5602, 5624, 5675, 5770, 5877, 5931, 5972, 6011, 6065, 6213, 6217, 6276, 6403, 6464, 6531, 6806, 6930, 7079, 7416, 7497, 7657, 7803, 7982, 8086, 8155, 8220, 8340, 8377, 8485, 8568, 8572, 8648, 8677, 8695, 8699, 8730, 8775, 8795, 8806, 8859, 9072, 9198, 9270, 9297, 9710, 9746, 9768, 9795, 9799, 9874, 9928, 9947]53729insertSort[9935, 9891, 9857, 9669, 9326, 9181, 9098, 9074, 8984, 8941, 8926, 8715, 8693, 8518, 8204, 8074, 8065, 7972, 7969, 7913, 7841, 7840, 7722, 7591, 7534, 7506, 7456, 7292, 7253, 7102, 6867, 6571, 6546, 6516, 6451, 6427, 6319, 6131, 6016, 5956, 5863, 5820, 5818, 5807, 5536, 5368, 5314, 5279, 5219, 5126, 5124, 5079, 5036, 4895, 4669, 4661, 4611, 4509, 4355, 4341, 4174, 4154, 3961, 3942, 3748, 3545, 3289, 3140, 3013, 2913, 2903, 2800, 2766, 2766, 2744, 2685, 2666, 2662, 2555, 2482, 2398, 2226, 2183, 2131, 2113, 2105, 1966, 1949, 1929, 1746, 1577, 1369, 1238, 1154, 902, 702, 636, 407, 378, 357]87703Arrays.sort[262, 367, 452, 530, 678, 725, 814, 980, 1109, 1168, 1271, 1345, 1391, 1458, 1497, 1527, 1813, 1847, 1848, 1927, 2034, 2149, 2211, 2509, 2608, 2974, 2990, 3003, 3250, 3283, 3333, 3485, 3693, 3697, 3707, 3833, 3865, 4062, 4246, 4254, 4566, 4571, 4722, 4820, 4839, 5010, 5038, 5140, 5358, 5383, 5393, 5561, 5660, 5912, 5913, 5943, 6120, 6206, 6279, 6376, 6723, 6772, 6892, 7027, 7044, 7049, 7135, 7367, 7462, 7519, 7595, 7609, 7662, 7730, 7752, 7811, 8028, 8039, 8049, 8066, 8171, 8193, 8226, 8263, 8318, 8629, 8664, 8796, 8861, 8910, 8999, 9313, 9497, 9589, 9674, 9679, 9772, 9820, 9860, 9958]367802mergeSort[17, 57, 94, 241, 278, 282, 557, 581, 593, 651, 860, 908, 1168, 1201, 1696, 1707, 1795, 1961, 2380, 2381, 2386, 2570, 2589, 2599, 2622, 2629, 2677, 2701, 2748, 2756, 2810, 2862, 3039, 3073, 3839, 3844, 3844, 3915, 4040, 4154, 4386, 4404, 4628, 4742, 4848, 4876, 5262, 5514, 5742, 5779, 5800, 5811, 5865, 5881, 6010, 6222, 6226, 6297, 6467, 6674, 6819, 6959, 7077, 7131, 7147, 7298, 7351, 7381, 7504, 7542, 7584, 7676, 7700, 7738, 7828, 7875, 7929, 7968, 8062, 8104, 8225, 8300, 8351, 8409, 8934, 8965, 8972, 8989, 9039, 9084, 9214, 9326, 9460, 9481, 9562, 9667, 9820, 9837, 9839, 9851]89283shellSort[9839, 9827, 9733, 9656, 9428, 9244, 9234, 9230, 9024, 8978, 8937, 8792, 8774, 8747, 8736, 8724, 8613, 8459, 8215, 8202, 8138, 7930, 7876, 7827, 7778, 7746, 7403, 7235, 6957, 6806, 6655, 6648, 6624, 6497, 6343, 6301, 6224, 6188, 6112, 6071, 5860, 5831, 5819, 5789, 5763, 5690, 5644, 5620, 5578, 5562, 5239, 5224, 5044, 5034, 4986, 4870, 4848, 4658, 4573, 4324, 4314, 3815, 3681, 3548, 3467, 3420, 3177, 3147, 3138, 3071, 2940, 2938, 2866, 2831, 2460, 2424, 2351, 2285, 2280, 2170, 2145, , 1906, 1857, 1733, 1282, 1081, 981, 795, 785, 755, 498, 409, 357, 345, 326, 124, 93, 81, 62]80197heapSort[91, 289, 327, 355, 583, 636, 704, 710, 810, 848, 860, 897, 946, 1122, 1180, 1234, 1258, 1358, 1393, 1667, 1690, 1773, 1779, 1906, 1919, , , 2055, 2123, 2135, 2212, 2580, 3109, 3724, 4162, 4309, 4440, 4469, 4675, 4721, 4869, 4948, 5029, 5037, 5065, 5185, 5357, 5490, 5535, 5548, 5615, 5635, 5750, 5780, 5785, 5874, 5934, 6094, 6238, 6271, 6301, 6309, 6337, 6458, 6530, 6550, 6581, 6618, 6625, 6640, 6683, 6742, 6946, 6960, 7006, 7013, 7017, 7036, 7108, 7424, 7435, 7551, 7573, 7651, 7707, 7883, 7927, 8246, 8521, 8567, 8651, 8752, 9190, 9210, 9212, 9425, 9608, 9709, 9907, 9935]129976radixSort[105, 137, 162, 278, 314, 448, 511, 721, 769, 770, 805, 1012, 1106, 1116, 1246, 1445, 1537, 1567, 1735, 1895, 2040, 2094, 2114, 2220, 2273, 2298, 2394, 2397, 2397, 2441, 2666, 2830, 2862, 2865, 2888, 3079, 3179, 3260, 3488, 3577, 3622, 3634, 4048, 4277, 4476, 4754, 5017, 5046, 5055, 5056, 5072, 5175, 5402, 5530, 5550, 5609, 5617, 5686, 5692, 5857, 5915, 5949, 6210, 6236, 6480, 6586, 6593, 6637, 6781, 6837, 6906, 7219, 7311, 7342, 7528, 7575, 7717, 7841, 7844, 7893, 7904, 7935, 8136, 8159, 8271, 8433, 8469, 8519, 8670, 8707, 8878, 8905, 8944, 9085, 9133, 9182, 9564, 9685, 9799, 9981]404542
一百个无规则数据排序，快排和希尔排序表现出优异的性能，而低数据量排序，则插入排序表现出优异的性能，我尝试的是十个；可以用这些demo多做尝试；关于原理网上有太多描述，大家自行百度。
选择排序 冒泡排序 插入排序 快速排序 希尔排序 归并排序 堆排序和希尔排序的java实现比较
如果觉得《选择排序 冒泡排序 插入排序 快速排序 希尔排序 归并排序 堆排序和希尔排序的ja》对你有帮助，请点赞、收藏，并留下你的观点哦！
