【排序算法】java实现
1.冒泡排序
最简单的排序实现，冒泡排序，是一种交换排序，它的基本思想是：凉凉比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
//冒泡排序privateint[]bubbleSort(int[] arr){for(inti =0;
i < arr.length;
i++)for(intj = arr.length -1;
j > i;
j--)if(arr[j] < arr[j -1]) {swap(arr, j, j -1);
}returnarr;
}
swap方法
privatevoidswap(int[] arr,inti,intj){inttemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
冒泡算法的优化（外部循环优化）
privateint[] bubbleSort1(int[] arr) {booleanflag =true;
//加入flag指针，若在一次冒泡中，没有交换 则说明可以停止 减少运行时for(inti =0;
i < arr.length && flag;
i++) {flag =false;
for(intj = arr.length -1;
j > i;
j--) {if(arr[j] < arr[j -1]) {swap(arr, j, j -1);
flag =true;
}}}returnarr;
}
代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义的循环判断。
优化2：
privateint[] bubbleSort2(int[] arr) {booleanflag =true;
//加入flag指针，若在一次冒泡中，没有交换 则说明可以停止 减少运行时intpos =0;
intk = arr.length -2;
for(inti =0;
i < arr.length && flag;
i++) {flag =false;
for(intj = arr.length -1;
j > k;
j--) {if(arr[j] < arr[j -1]) {swap(arr, j, j -1);
flag =true;
pos = i;
}k = pos;
}}returnarr;
}
冒泡排序的复杂度。当最好情况，也就是要排序的表本身就是有序的，那么我们要比较次数，根据改进后的代码，可以判断出就是n-1次比较，没有数据交换，时间复杂度也就是O(n).当最坏情况，即待排序表是逆序的情况，此时需要比较1+2+3+.....+(n-1) = n(n-1)/2次，并作等数量级的移动记录。因此，总的 时间复杂度为O(n 2 )。
2.简单选择排序
基本思想：每一趟（例如第i趟）在n-i(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录，直到第n-1趟做完，待排序元素只剩1个，就不用再选了。
privateint[] selectSort(int[] arr) {intmin;
for(int i =0;
i < arr.length -1;
i++) {//共进行n-1趟min= i;
//记录最小元素位置for(int j = i +1;
j < arr.length;
j++) {if(arr[j] < arr[min]) {min= j;
//更新最小元素}}if(min!= i) {swap(arr, i,min);
}}returnarr;
}
简单选择排序的思想很简单，代码也很清晰就不多加赘述。
复杂度： 从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间，分析它的时间复杂度发现，无论最好最差情况，其比较次数都是一样多的，第i趟排序需要进行 n-1 次关键字的比较，此时需要比较n-1+n-2+...+1 = n(n-1)/2次。而对于交换次数而言，当最好情况，交换次数为0，最差情况，也就是逆序时，交换次数n-1次，基于最终的排序时间是比较与交换次数的综合，因此总的时间复杂度依然为O(n 2 ).
应该说，尽管与冒泡排序同为O(n 2 ),但简单选择排序的性能上还是要略由于冒泡排序的。
3.直接插入排序
基本思想：将一个记录插入到已经排序的有序表中，从而得到一个新的、记录数增1的有序表
privateint[]insertSort(int[] arr){inttemp =0;
intj =0;
for(inti =1;
i < arr.length;
i++) {temp = arr[i];
for(j = i;
j >0&& temp < arr[j-1];
j--) {arr[j] = arr[j -1];
// 假如temp比前面的值小，则将前面的值后移}arr[j] = temp;
}returnarr;
}
【【排序算法】java实现】复杂度分析：从控件上来看，它只需要一个记录的辅助空间。时间复杂度，O(n 2 )但是性能比简单选择排序和冒泡排序要好一些。
4.希尔排序（缩小增量排序）
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
privateint[] shellSort(int[] arr) {intj;
inttemp =0;
//每次将步长缩小为1/2for(intd = arr.length/ 2;
d > 0;
d /=2) {for(inti = d;
i < arr.length;
i++) {temp = arr[i];
for(j = i;
j >= d;
j -= d) {if(temp < arr[j - d]) {arr[j] = arr[j - d];
}else{break;
}}arr[j] = temp;
}}returnarr;
}
时间复杂度O(n^1.5）
5.堆排序
基本思想:堆排序（heap sort）就是利用堆进行排序的方法。将待排序的序列构造成一个堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素蒋欢，此时元素末尾就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。
按照这个思想来做，那么实际会有两个问题：
如何由一个无需序列构建成一个堆？
如何再输出堆顶元素后，调整生于元素成为一个新的堆？
privateint[]heapSort(int[] arr){inti;
for(i = arr.length /2;
i >=0;
i--) {//把arr构建成大顶堆heapAdjust(arr, i, arr.length -1);
}for(i = arr.length -1;
i >=0;
i--) {swap(arr,0, i);
//将堆顶元素和当前未经排序子序列的最后一个记录交换heapAdjust(arr,0, i -1);
//重新调整大顶堆}returnarr;
}privatevoidheapAdjust(int[] arr,ints,intm){//已知arr[s...m]中记录的关键字除了arr[s]之外均满足堆的定义//本函数调整arr[s]的关键字，使arr[s...m]成为一个大顶堆inttemp, j;
temp = arr[s];
for(j =2* s;
j <= m;
j *=2) {//沿关键字较大的孩子节点往下筛选if(j < m && arr[j] < arr[j +1]) {++j;
//j为关键字中较大的记录的下标}if(temp >= arr[j]) {break;
//应插入在位置s上}arr[s] = arr[j];
s = j;
}arr[s] = temp;
//插入}
时间复杂度O(nlogn）不适合待排序序列较少的情况
6.归并排序
归并排序（merging sort）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
privateint[]mergeSort(int[] arr){returnmSort(arr,0, arr.length -1);
}privateint[]mSort(int[] arr,intlow,inthigh){intmid = (low + high) /2;
if(low < high) {//左边mSort(arr, low, mid);
//右边mSort(arr, mid +1, high);
//左右归并merge(arr, low, mid, high);
}returnarr;
}privatevoidmerge(int[] arr,intlow,intmid,inthigh){int[] temp =newint[high - low +1];
inti = low;
// 左指针intj = mid +1;
// 右指针intk =0;
// 把较小的数先移到新数组中while(i <= mid && j <= high) {if(arr[i] < arr[j]) {temp[k++] = arr[i++];
}else{temp[k++] = arr[j++];
}}// 把左边剩余的数移入数组while(i <= mid) {temp[k++] = arr[i++];
}// 把右边边剩余的数移入数组while(j <= high) {temp[k++] = arr[j++];
}// 把新数组中的数覆盖nums数组if(temp.length >=0) System.arraycopy(temp,0, arr, low, temp.length);
}
时间复杂度O(nlogn）
7.快速排序
基本思想：分治
privateint[]quickSort(int[] arr){returnqSort(arr,0, arr.length -1);
}privateint[]qSort(int[] arr,intlow,inthigh){if(low < high) {intpivotPos = partition(arr, low, high);
//划分qSort(arr, low, pivotPos -1);
qSort(arr, pivotPos +1, high);
}returnarr;
}privateintpartition(int[] arr,intlow,inthigh){//一趟排序过程intpivot = arr[low];
//将当前表的第一个元素作为枢轴值，对表进行划分while(low < high) {//循环跳出条件while(low < high && arr[high] >= pivot) --high;
arr[low] = arr[high];
//将比pivot小的移到左侧while(low < high && arr[low] <= pivot) ++low;
arr[high] = arr[low];
//将比pivot大的移到右侧}arr[low] = pivot;
//枢轴元素存放到最终位置returnlow;
//返回枢轴的最终位置}
时间复杂度O(nlogn）
快速排序在序列中元素很少时，效率将比较低，不如插入排序，因此一般在序列中元素很少时使用插入排序，这样可以提高整体效率。
我自己是一个从事了6年的Java全栈工程师，最近整理了一套适合2019年学习的Java\大数据资
料，从基础的Java、大数据面向对象到进阶的框架知识都有整理哦，可以来我的主页免费领取哦。
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长