第一篇博客，从几种排序算法开始

简单插入排序

   插入排序，即是假设数组的前 i-1个元素有序（i从1开始），当轮到第i个元素时，只需要找到第i个数在前i-1个元素中的位置，并将这个数值插入，一言以蔽之即为 找准位置插入

代码实现

/*** 简单插入排序* 从第一个元素开始，该元素可以认为已经被排序；* 取出下一个元素，在已经排序的元素序列中从后向前扫描；* 如果该元素（已排序）大于新元素，将该元素移到下一位置；* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；* 将新元素插入到该位置后；* 重复步骤2~5。*/
public class SimpleInsertionSort {public int[] insertionSort(int[] arrs) {int n = arrs.length;if (arrs == null || n < 2) return arrs;for (int i = 1; i < n; i++) {int cur = arrs[i];int j = i - 1;while (j >= 0 && arrs[j] > cur) {arrs[j + 1] = arrs[j];j--;}arrs[j+1]=cur;}return arrs;}public static void main(String[] args) {SimpleInsertionSort simpleInsertionSort=new SimpleInsertionSort();int[] arrs={45,5,68,6,59,755,69,21,456};System.out.println(simpleInsertionSort.insertionSort(arrs));}
}

希尔排序

    嘛是希尔排序，上面说的简单插入排序在面对大致有序的数组时还是很不错的，但是当数组顺序混乱甚至逆序时，比较次数实在太多，那么可以对上面的简单插入算法进行改进，改进方向为使无序的数组变得大致有序，即对数组进行划分分组，对组内元素进行插入排序，且不断缩小分组大小，直到分组大小为1

  代码实现

/*** 希尔排序* 是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。* 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；* 按增量序列个数k，对序列进行k 趟排序；* 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。*/
public class ShellSort {public int[] shellSort(int[] arrs){int n=arrs.length;if(arrs==null||n<2)return arrs;//进行分组 初始分组长度为n/2,依次为上一次的1/2int d=n;while (d>0){d/=2;//循环插入排序d组for(int i=0;i=0&&arrs[t]>temp){arrs[t+d]=arrs[t];t-=d;}arrs[t+d]=temp;}}}return arrs;}public static void main(String[] args) {ShellSort shellSort=new ShellSort();int[] arrs={45,5,68,6,59,755,69,21,456};System.out.println(shellSort.shellSort(arrs));}
}

快速排序

      百度上说快速排序是冒泡排序算法的改进，截图如下：

    排序过程：

• 遍历一遍数组，找到一个位置，这个位置特点：该点左边的数都比他小&&该点右边的数都比他大（该过程存在数据交换）
•        再分别遍历该位置左边和右边的数组 ，分别找到这个位置
• 递归执行上述过程

代码实现

/*** 快速排序* 快速排序的基本思想：*      通过一趟排序将待排记录分隔成独立的两部分，*      其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。*/
public class QuickSort {public int[] quickSort(int[] arrs){arrs=  quickSort(arrs,0,arrs.length-1);return arrs;}private int[] quickSort(int[] arrs,int low,int hight){if(low=midValue) j--;if(i>=j)break;swap(arrs,i,j);}arrs[low]=arrs[j];arrs[j]=midValue;return j;}private void swap(int[] arrs,int i,int j){int temp=arrs[i];arrs[i]=arrs[j];arrs[j]=temp;}public static void main(String[] args) {QuickSort quickSort=new QuickSort();int[] arrs={45,5,68,6,59,755,69,21,456};System.out.println(quickSort.quickSort(arrs));}
}

堆排序

   堆排序，关键字：堆，即利用大顶堆（小顶堆）这个特殊的数据结构进行排序

   大顶堆数据结构特点：

                 1:一个完全二叉树

                 2:父节点的值要大于左子树和右子树的值

因为堆是个完全二叉树，立即推：最后一个非叶子节点在数组中的下标为，第i个元素的叶子节点的下标为2i+1,2i+2。

排序过程：

• 将数组构造为一个大顶堆，此时堆顶为最大值
• 将堆顶与最后一个元素交换
• 将前i-1个元素再次构造成大顶堆
• 循环执行以上两过程

代码实现

/*** 堆排序* 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。* 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。* 
* 1将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;* 　　2将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;* 　　3重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。*/
public class HeapSort {public int[] heapSort(int[] arrs) {int n = arrs.length;if (arrs == null || n < 2) return arrs;for (int i = n / 2 - 1; i >= 0; i--) {adjustHeap(arrs, i, n);}for (int j = n - 1; j > 0; j--) {swap(arrs, 0, j);adjustHeap(arrs, 0, j);}return arrs;}public void adjustHeap(int[] arrs, int i, int len) {int temp = arrs[i];for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {if (k + 1 < len && arrs[k] < arrs[k + 1]) {k++;}if (arrs[k] > temp) {arrs[i] = arrs[k];i = k;} else {break;}}arrs[i] = temp;}private void swap(int[] arrs, int i, int j) {int temp = arrs[i];arrs[i] = arrs[j];arrs[j] = temp;}public static void main(String[] args) {HeapSort heapSort=new HeapSort();int[] arrs={45,5,68,6,59,755,69,21,456};heapSort.heapSort(arrs);}
}

二路归并排序

     归并排序思想，即数组长度太长，那就将数组不断进行“1/2”式的切分，分别对各“1/2”子数组进行排序，最后将两个有序的数组合并为一个有序的数组.（二分法）

    代码实现

/*** 二路归并排序* 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。* 若将两个有序表合并成一个有序表，称为2-路归并。*/
public class TwowayMergeSort {public int[] mergeSort(int[] arrs) {int n = arrs.length;if (arrs == null || n < 2) return arrs;arrs = sort(arrs, 0, n - 1);return arrs;}public int[] sort(int[] arrs, int left, int right) {if (left == right) return arrs;int mid = left + (right - left) / 2;sort(arrs, left, mid);sort(arrs, mid + 1, right);merge(arrs, left, mid, right);return arrs;}public void merge(int[] arrs, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, t = 0;while (i <= mid && j <= right) {if (arrs[i] < arrs[j]) {temp[t++] = arrs[i++];} else {temp[t++] = arrs[j++];}}while (i <= mid)temp[t++] = arrs[i++];while (j <= right)temp[t++] = arrs[j++];for (int k = 0; k < right - left + 1; k++) {arrs[left + k] = temp[k];}}public static void main(String[] args) {TwowayMergeSort twowayMergeSort = new TwowayMergeSort();int[] arrs = {45, 5, 68, 6, 59, 755, 69, 21, 456};arrs = twowayMergeSort.mergeSort(arrs);for (int arr : arrs) {System.out.print(arr + " ");}}
}

计数排序

       关键词：计数。

       计嘛数？数组中各个元素出现的个数。

       排序过程：

•  遍历数组：找到数组中的最大值Max
•  创建一个新数组（初始值都为0），新数组长度为Max+1。为什么是Max+1?  因为从0到Max有Max+1个数（即数组中元素的值对应为新建数组的下标）
•  再次遍历数组，将其对应的新数组元素值＋1
•  遍历新数组，将值不为0的元素下标依次输出

       适用范围（局限性）

            通过上述描述可知，计数排序是根据数组中最大值来确定新建数组长度，则立即推：当数组值较为分散，例如{0,10000}时，则需要新建10001长度的数组，且只有两个元素被使用，造成极大的空间浪费。并且当数组元素存在负数时，亦不适用，即找不到下标为负数的数组。

       代码实现

/*** 计数排序* 将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。* 找出待排序的数组中最大和最小的元素；* 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；* 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；* 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。*** 适用于数组大小范围确定且不大*/
public class CountSort {public  int[] countSort(int[] arrs){if(arrs==null||arrs.length<2)return arrs;//找到arrs中的最大值int max=arrs[0];for(int v:arrs){max=v>max?v:max;}//创建长度为max+1（0~max）的数组int[] countArr=new int[max+1];//累加结果for(int v:arrs){countArr[v]++;}//遍历结果int j=0;for(int i=0;i0){arrs[j++]=i;countArr[i]--;}}return arrs;}public static void main(String[] args) {CountSort countSort=new CountSort();int[] arrs={0, 1, 1, 2, 3, 3, 3, 4, 8, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10};countSort.countSort(arrs);for (int arr : arrs) {System.out.print(arr + " ");}}
}

桶排序

     上述的计数排序存在其局限性，桶排序为计数排序的改进。

     桶排序中，可创建若干个桶（List获取其他容器类，类似计数排序中new的数组），每个桶中装有一定数量的数组元素，分别对每个桶中的元素进行排序，而后根据桶的顺序依次输入。

     问题来了：

       应该创建多少个桶？

               个人理解，桶的数量与数组元素的分布情况有关，例如，在元素范围为（-50,100），每个桶的装取范围为20，则桶的数量应为（100-（-50））/20。当然，这与映射函数有关。

       桶应该装哪些元素？

                 这个问题则与映射函数有关系，桶排序的高效与否与映射函数直接相关，差的映射函数会将所有元素统统装入同一桶中，好的映射函数则会将数据均匀的映射如不同的桶中。

     排序过程

• 遍历数组，获取最小值min和最大值max
• 定义桶的装取范围为10，并创建（max-min）/10+1个桶
• 遍历数组，数组元素对应的下标为idx=(arrs[i]-min)/10，将此元素放入第idx桶中（idx=(arrs[i]-min)/10为映射函数）
• 对每个桶进行排序（排序算法随意）
• 每个排好序的桶依次输出

     代码实现

/*** 桶排序*将数据分段放入不同的桶中*对桶中元素进行排序* 根据桶顺序依次输入* 需要额外的空间*/
public class BucketSort {public  int[] bucketSort(int[] arrs){if(arrs==null||arrs.length<2)return arrs;bucketSort0(arrs,10);return arrs;}public void bucketSort0(int[] arrs,int bucketSize){//1.获取数组最大值和最小值int max=arrs[0],min=arrs[0];for(int v:arrs){max=max>v?max:v;min=min> buckets=new ArrayList<>(bucketCount);for(int i=0;i());}//将数组数据映射到不同的桶中for(int v:arrs){int idx=(v-min)/bucketSize;buckets.get(idx).add(v);}//对各桶进行排序for(List bucket:buckets){if(bucket.size()>0){Collections.sort(bucket);}}//将桶中数据依次写回；int j=0;for(List bucket:buckets){for(Integer value:bucket){arrs[j++]=value;}}}public static void main(String[] args) {BucketSort bucketSort=new BucketSort();int[] arrs={-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70};bucketSort.bucketSort(arrs);for (int arr : arrs) {System.out.print(arr + " ");}}
}

适用范围（局限性） 

   数组元素符合均匀分布

基数排序

  基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。

 排序过程

• 遍历数组，找到最大值，并计算其位数n，构建10个桶
• 分别遍历数组元素，根据其第i位的值映射如对应的桶中（分配）
• 依次将每个桶中的元素依次写入原数组（收集）
• 循环执行上两过程n次

 代码实现      

/*** 基数排序* 取得数组中的最大数，并取得位数；* arr为原始数组，从最低位开始取每个位组成radix数组；* 对radix进行计数排序（利用计数排序适用于小范围数的特点）；*/
public class RadixSort {public int[] radoxSort(int[] arrs){if(arrs==null||arrs.length<2)return arrs;int max=arrs[0];int mod=10;int div=1;//获取最大值for(int v:arrs){max=max>v?max:v;}int maxDigit=0;while (max>0){max/=10;maxDigit++;}//初始化桶List> buckets=new ArrayList<>(10);for(int i=0;i<10;i++) buckets.add(new ArrayList<>());for(int i=0;i bucket:buckets){for(int val:bucket){arrs[j++]=val;}bucket.clear();}}return arrs;}public static void main(String[] args) {RadixSort radixSort=new RadixSort();int[] arrs={45,5,68,6,59,755,69,21,456};radixSort.radoxSort(arrs);for (int arr : arrs) {System.out.print(arr + " ");}}
}

总结

各个排序算法比较

如图

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！