网站首页 文章专栏 java几种典型的排序,冒泡,插入,选择等
相关术语说明:
稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
时间复杂度: 一个算法执行所耗费的时间。
空间复杂度:运行完一个程序所需内存的大小。
几种算法的空间复杂度以及时间复杂度
冒泡排序 :冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 |
1.1 算法思路描述:
比较相邻的元素。如果第一个比第二个大,就交换它们两个;
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
针对所有的元素重复以上的步骤,除了最后一个;
重复步骤1~3,直到排序完成。
1.2 动图演示
1.3 代码
public static void name(int[] arr,int length) { for(int i=0; i< length - 1; i++){ for(int j = 0; j < length - 1 - i; j++){ if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
冒泡排序虽然简单,但是还是有可以优化的地方,下面为冒泡排序的优化版本
/** * 改进版冒泡排序,主要维护了一个尾部边界索引,如果交换到后面不需要交换,则下次遍历后面无需遍历 * @param arr * @param length */ public static void bubbleSort(int[] arr,int length){ int flag = length; int lastIndex; while(flag > 0){ lastIndex = flag; flag = 0; for(int i = 1;i < lastIndex;i++){ if(arr[i] < arr[i - 1]){ int temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; flag = i; } } } }
插入排序 :插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。 |
2.1 算法思路描述:
第一趟比较前两个数,然后把第二个数按大小插入到有序表中
第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;
依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程
2.2 图示
2.3 代码演示
/** * 插入排序 * @param arr * @param length */ public static void insertionSort(int[] arr,int length){ for(int i = 1; i < length; i++){ for(int j = i; j > 0 && arr[j] < arr[j - 1];j--){ int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } }
同样,插入排序也是可以优化的。
/** * 插入排序 * @param arr * @param length */ public static void insertionSort(int[] arr,int length){ //改进版,不需要每次都交换,而是将该值拿出来,与前面对比,如果比前面小,则将前面一个赋值给后面一个,直到前面没有更小的,此时将该值赋值给当前 for(int i = 1; i < length; i++){ int e = arr[i]; int j; for(j = i; j > 0 && arr[j - 1] > e;j--){ arr[j] = arr[j - 1]; } arr[j] = e; } }
选择排序 :第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 |
3.1 算法思路描述:
第一趟:从n个记录中找出关键码最小的记录和第一个记录交换;
第二趟:从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换,以此类推......
第i趟,则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换,直到整个序列按关键码有序。
3.2 图示
3.3 代码演示
/** * 选择排序 */ public static void selectSort(int[] arr,int length){ for(int i = 0;i < length; i++){ int minIndex = i; for(int j = i + 1; j < length;j++){ if(arr[j] < arr[minIndex]){ minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }
总结:几种算法的思想大体类似,关键在于交界点的思考,不然容易出错,下次研究快速排序以及归并排序。
版权声明:本文由星尘阁原创出品,转载请注明出处!