几种排序算法的Java实现
最近对几种排序算法进行了梳理
1、冒泡排序
- 算法思想： 依次和相邻的数进行比较，这样每一次出发都把最大的放到了最后一个
- 时间复杂度 n的平方
*实现 代码
public int [] bubbleSort (int[] a ){//冒泡排序//记得对一个数组进行排序前先判断这个诗数组是不是为空if (a.length ==0) {return a;}for (int i = 0; i < a.length-1; i++) {for (int j = 0; j < a.length-1-i; j++) {if (a[j+1]<a[j]) {int temp = a[j+1];a[j+1] = a[j];a[j] = temp;}}}//冒泡排序的优化利用标记比较不用排序的位置/* boolean flag = false;for (int i = 0; i < a.length-1; i++) {flag = false;for (int j = i; j < a.length-1-i; j++) {if (a[j+1]<a[j]) {int temp = a[j+1];a[j+1] = a[j];a[j] = temp;flag = true;}if (flag =false){break;}}}*/return a;}
2 快速排序
思想：
（1）找到一个key值
（2）先走一趟，进行交换，把比key小的都放到key前面，把比key大的都放到key后面，key和i的位置互换
（3）这样调用递归分别对key值前后的分段数据再进行排序
*/public int[] quicksort (int [] a){//int [] b = new int[ARRY_LENGT];if (a.length>0) {quicksort(a, 0 , a.length-1);}return a;}private void quicksort(int[] a, int low, int high) {//1.找到递归算法的出口if(low>high){return;}int start = low;int end = high;int key = a[low];while(end>start){//从后往前比较while(end>start&&a[end]>=key) //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较end--;if(a[end]<=key){int temp = a[end];a[end] = a[start];a[start] = temp;}//从前往后比较while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置start++;if(a[start]>=key){int temp = a[start];a[start] = a[end];a[end] = temp;}//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用}//递归if(start>low) quicksort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1if(end<high) quicksort(a,end+1,high);//右边序列。从关键值索引+1到最后一个}
3.插入排序
/*
插入排序，插入排序是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，
在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，
为最新元素提供插入空间。
算法分析 最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
*/
public static int[] insertSort(int[] ins){for(int i=1; i<ins.length; i++){int temp = ins[i];//保存每次需要插入的那个数int j;for(j=i; j>0&&ins[j-1]>temp; j--){//这个较上面有一定的优化ins[j] = ins[j-1];//把大于需要插入的数往后移动。最后不大于temp的数就空出来j}ins[j] = temp;//将需要插入的数放入这个位置}return ins;}
4.希尔排序
希尔排序(希尔排序是插入排序的一种优化)，将所有的数据记性分段，然后按列进行排序，依次减小排序的成本
（1）分组
（2）列排序
（3）分组步数减小，再次分组
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
*/
public int [] shellSort(int [] a){
int len = a.length;
int tem,gap=len/2; //gap就是长度的一半，步长
while (gap>0) {for (int i =gap; i < len ; i++) {tem = a[i];int preindex = i-gap;while (preindex>0&&a[preindex] > tem) {a[preindex+gap] = a[preindex];preindex -= gap;}a[preindex+gap]=tem;}}return a;}
5.选择排序
- 思想：（1）们每次排序找到最小的数，记录原始位置
- （2）置换到应该有的位置
- 平均时间复杂度 n2，最坏时间复杂度n2
*/
public int [] selectSort(int [] a){
for (int i = 0; i < a.length-1; i++) {
int k=i;
for (int j = k+1; j < a.length; j++) {if (a[j]<a[k]) {k=j; //记下目前查找到的最小值所对应的位置}//内层一次循环结束开始进行比较if (k!=i) {int tem =a[i];a[i]=a[k];a[k]=tem;}}}return a;
}
主函数public static void main(String[] args) {
// TODO Auto-generated method stub
sort mSort =new sort(); //new新的对象的同时调用构造函数进行初始化//冒泡排序long start=System.currentTimeMillis(); //获取系统当前时间System.out.print("冒泡排序:");int bubblesort[]=mSort.bubbleSort(mSort.CopyArrayData());long end=System.currentTimeMillis(); //mInternalSort.printArray(bubblesort);
太过爱你忘了你带给我的痛
ゝ一纸荒年。
怼烎@
港控/mmm°
还没有评论，来说两句吧...