Java数据结构与算法–简单排序
- 2019 年 11 月 21 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/wangtongxue123456/article/details/72638485
简单排序
本文讨论比较简单的排序算法：冒泡排序、选择排序、插入排序
三个算法都包括如下两个步骤。
- 比较两个数据项
- 交换两个数据项、或复制其中一项。
冒泡排序
冒泡排序算法运行起来非常慢，但是在概念上他是排序算法中最简单的。
冒泡排序遵循的规则： 1. 比较两个数据 2. 如果左边的数据大，则两个数据交互位置。 3. 向右移动一个位置，比较下面两个数据。（沿着这个队列一直比较下去，一直比较到队列的最右端），这时最右端的数据应该会是最大的数。 4. 当碰到第一个排定的数据后，就返回队列的左端重新开始下一趟排序。 代码实现
/** * 冒泡排序 */ public class BubbleSort { //初始化数组 private static long a[]=new long[]{11,4,7,9,2,10,23,8,34,29}; //数组长度 private static int nElems=a.length; public static void main(String[] args) { int in,out; for (out=nElems-1;out>1;out--){ // for (in=0;in<out;in++){ //比较相邻的元素。如果第一个比第二个大，就交换他们两个。 if (a[in]>a[in+1]){ swap(in,in+1); } } } //输出排序 for (long l:a){ System.out.print(l+" "); } } //交换数据 private static void swap(int in, int i) { long temp=a[in]; a[in]=a[in+1]; a[in+1]=temp; }
算法思路 １.将最小的数据项放在数组的最开始，并将最大的数据项放在数组的最后。 ２.外层for 循环的计数器out从数组的最后开始，没经过一次循环ｏｕｔ减一。下标大于ｏｕｔ的数据项都是已经排好序的，变量ｏｕｔ每完成一次内部循环（计数器为ｉｎ）后就左移一位。 ３.内层ｆｏｒ循环计数器ｉｎ从数组的最开始算起（ｉｎ＝０），没完成一次内部循环体加一，当它等于ｏｕｔ时结束一次循环，在内层ｆｏｒ循环体重，数组下标ｉｎ和ｉｎ＋１的两个数据项进行比较，如果ｉｎ数据大于ｉｎ＋１数据项，则交换数据。 ４.为了清晰增加独立的ｓｗａｐ（）方法执行交换，但是它会增加一些额外的消耗，如果自己使用排序程序，最好将交换操作这段代码直接放到程序中。这样可以提高一些速度。
选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
代码实现
/** * Created by YcDr on 2017/5/24. * 选择排序 */ public class SelectSort { //初始化数组 private static long a[]={12,34,19,2,54,13,11,33,18,9}; //数组长度 private static int nElems=a.length; public static void main(String[] args) { int in,out,temp; for (out=0;out<nElems;out++){ temp=out;//temp临时变量，用于存取最小值下标 for (in=out+1;in<nElems;in++){ if (a[temp]>a[in]){ temp=in; } } //每次循环找出最小值下标后，在进行数据交换 swap(out,temp); } for (long l:a) System.out.print(l+" "); } //交换数据 private static void swap(int i,int t) { long temp=a[t]; a[t]=a[i]; a[i]=temp; } }
与冒泡排序比较
选择排序与冒泡排序相比，都执行了相同的比较次数N*(N-1)/2,但是相比冒泡排序，选择排序降低了交换数据的次数。 选择排序和冒泡排序一样运行了O（N^2）时间，但是显然选择排序要比冒泡排序更快一些，因为选择排序交换次数很少，如果交换时间及比比较时间及要大的多时，选择排序实际要快的多。
插入排序
在大多数情况下，插入算法是本章描述的基本排序算法中最后的一种，虽然插入排序算法任然需O(N^2) 的时间，但是在一般情况下他要比冒泡排序快一倍，比选择排序还要快一点。
算法思路 1. 默认序列中的第0个元素是有序的； 2. 从下标为1（下标从0开始）的元素开始，取当前下标i位置处的元素a[i]保存到一个临时变量里； 3. 对前半部分有序序列的循环遍历，并与临时变量比较，直到遇到一个比临时变量小的元素（这里默认是从小到大排序），交换数据 4. 将待插入元素的下标 i 向后推移一个位置； 5. 重复进行第2步到第4步，直到乱序序列中的元素被全部插入到有序序列中；
代码实现
/** * Created by YcDr on 2017/5/25. * 插入排序 */ public class InsertSort { //初始化数组 private static long a[]={12,19,34,2,54,13,11,33,18,9}; //数组长度 private static int nElems=a.length; public static void main(String[] args) { int in,out; for (out=1;out<nElems;out++){ long temp=a[out]; in=out; while (in>0&&a[in-1]>=temp){ a[in]=a[in-1]; in--; } a[in]=temp; } for (long l:a){ System.out.print(l+" "); } } }
稳定性
有些时候，排序要考虑数据项拥有相同关键字的情况，例如，雇员姓名按字典进行排序，现在又想按邮政编码排序，并希望，让不需要排序的数据保持原来的排序。这种情况下，则只需要算法对需要排序的数据进行排序，让不需要的数据保持原来的顺序，某些算法满足这样的要求，他们就可以称为稳定的算法。
