九种常见排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了九种常见排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6465字，纯文字阅读大概需要10分钟。
内容图文
package mysort;
import org.apache.commons.lang.math.RandomUtils;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
/**
* 列举常用排序算法
*/
public class MySort {
/**
* 共列举7+2中排序算法
* 按平均时间复杂度分：
* O(n*n) 插入排序，冒泡排序，选择排序
* O(nlogn) 堆排序，归并排序，快速排序
* O(n) 桶排序
* 不好说 基数排序，希尔排序
* 按算法思想来分：
* 分治： 归并排序，快速排序
* 有点类似贪心： 堆排序，选择排序，插入排序
* Hash映射思想： 桶排序
* 需要借鉴的算法思想和数据结构：
* 分治思想：分+合
* 贪心：总是选择当前局部最优
* Hash映射
* 堆（二叉树）
* 二分查找
*/
/**
* 1.插入排序：遍历数组，包装遍历到的地方之前已经排好序，对第i个数字二分搜索插入的位置
* 当然也可以把要插入的那个元素遍历找到它应该在的位置
* 如果二分+用链表存储，时间复杂度降为O(nlogn)
*/
public static void insertBinarySort(int[] arr){
int len = arr.length;
for (int i = 1; i < len; i++) {
// 将第i个数放到已经拍好序的前i-1的有序数组中
int l = 0;
int r = i - 1;
while (l <= r){
int mid = l + ((r - l) >> 2); //不加括号的号似乎是先算加号再算 >>
if(arr[i] < arr[mid]){
r = mid - 1;
}else {
l = mid + 1;
}
}
// 至此，找到了第i个数位于第l和第r个数之间,如果用链表的话，明显不用遍历，插入复杂度为O(1)
int temp = arr[i];
for(int j = i; j > l; j --){
arr[j] = arr[j - 1];
}
arr[l] = temp;
System.out.println(Arrays.toString(arr));
}
}
/**
* 2.冒泡排序：不断遍历数组，每次遍历中，只保证遍历的元素和它前一个是排好序的，这种冒泡只保证较小数字会发生一次前移，最坏情况是
* 从数组最后移动到数组最前面
* 时间复杂度：O(n*n)
*/
public static void bubbleSort(int[] arr){
int len = arr.length;
for (int i = 0; i < len; i++) {
boolean earlyStop = true;
for(int j = 1; j < len; j ++){
if(arr[j] < arr[j - 1]){
earlyStop = false;
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
System.out.println(Arrays.toString(arr));
if(earlyStop) break;
}
}
/**
* 3.桶排序：有点hash的感觉，把数组元素的数值映射到新数组的索引，如果数值超大，好像复杂度就上去了
* 时间复杂度：O(n)
*/
public static void bucketSort(int[] arr) {
int len = arr.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// 求最小值和最大值
for (int i : arr) {
if(i < min) min = i;
if(i > max) max = i;
}
int[] bucket = new int[max - min + 1];
for (int i : arr) {
bucket[i - min] ++;
}
int index = 0;
for (int i = 0; i < bucket.length; i++) {
while (bucket[i] -- != 0){
arr[index ++] = i + min;
}
}
}
/**
* 4.堆排序：数组表示一颗完全二叉数，然后从数的下到上找到最大值，拿出后再重复上述步骤找到最大值
* 一般的堆排序要求构建号最大堆或者最小堆，实际上排序只需取出最大值即可，无需满足最大堆
* 时间复杂度：O(nlogn)
*/
public static void heapSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int last = (len - i - 2) / 2; // 需要开始处理的非叶子节点
for(int j = last; j >= 0; j --){
int childMaxIndex = 2*j + 1;
if(2*j + 2 < len - i && arr[2*j + 1] < arr[2*j +2]){
childMaxIndex = 2*j + 2;
}
if(arr[j] < arr[childMaxIndex]){
swap(arr,j,childMaxIndex);
}
}
swap(arr,0, len - i - 1);
System.out.println(Arrays.toString(arr));
}
}
// 交换data数组中i、j两个索引处的元素
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
/**
* 5.归并排序 分治思想
* 时间复杂度：O(nlogn)
*/
public static void mergeSort(int[] arr) {
mergeSortRecDiv(arr, 0, arr.length - 1);
}
private static void mergeSortRecDiv(int[] arr, int l, int r) {
if(l >= r) return;
mergeSortRecDiv(arr,l,l + ((r - l) >> 2));
mergeSortRecDiv(arr,l + ((r - l) >> 2) + 1,r);
mergeSortRealMerge(arr, l, r);
}
private static void mergeSortRealMerge(int[] arr, int l, int r) {
int mid = l + ((r - l) >> 2);
// 对[l,mid]和[mid,r]进行归并排序
int first = l;
int second = mid + 1;
int[] temp = new int[r - l + 1];
int tempIndex = 0;
while (tempIndex < r - l + 1){
if(first > mid){
temp[tempIndex ++] = arr[second ++];
continue;
}
if(second > r) {
temp[tempIndex ++] = arr[first ++];
continue;
}
if(arr[first] > arr[second]){
temp[tempIndex ++] = arr[second ++];
}else {
temp[tempIndex ++] = arr[first ++];
}
}
System.arraycopy(temp,0,arr,l,r - l + 1);
}
/**
* 6.快速排序 延伸问题：无序数组第k小元素
* 选定一个基数，假如a[0]，拿出来，从后找到第一个比它小的，填入a[0],此时刚刚的数又空出来，此时保证了空出来数的右边一定大于a[0],
* 再从0之后开始寻找第一个大于a[0]的数字填入上一个坑，此时找到的这个数字索引之前一定是小于a[0]，前后指针对撞后，保证了该指针指向
* 之前小于a[0]，之后大于a[0]，再分治即可
* 时间复杂度：O(nlogn)
*/
public static void quickSort(int[] arr){
subQuickSort(arr,0,arr.length-1);
}
private static void subQuickSort(int[] arr, int l, int r) {
if(l >= r) return;
int lsave = l;
int rsave = r;
int base = RandomUtils.nextInt(r - l + 1) + l;
int tempBase = arr[base];
swap(arr,l,base);
while (l < r){
while (l < r && arr[r] >= tempBase) -- r;
// 最坏情况是tempBase是最小值，此时r会减到l - 1
arr[l] = arr[r];
while (l < r && arr[l] <= tempBase) ++ l;
arr[r] = arr[l];
}
arr[l] = tempBase;
System.out.println(Arrays.toString(arr));
subQuickSort(arr,lsave,l - 1);
subQuickSort(arr,l + 1,rsave);
}
/**
* 快排的重要应用
* 无序数组第k小元素
* 时间复杂度：O(n)
*/
public static int kMinNumByquickSort(int[] arr, int k){
int result = subKMinNumQuickSort(arr,0,arr.length-1,k);
return result;
}
private static int subKMinNumQuickSort(int[] arr, int l, int r,int k) {
if(l > r) return Integer.MAX_VALUE;
int result = Integer.MAX_VALUE;
int lsave = l;
int rsave = r;
int base = RandomUtils.nextInt(r - l + 1) + l;
int tempBase = arr[base];
swap(arr,l,base);
while (l < r){
while (l < r && arr[r] >= tempBase) -- r;
// 最坏情况是tempBase是最小值，此时r会减到l - 1
arr[l] = arr[r];
while (l < r && arr[l] <= tempBase) ++ l;
arr[r] = arr[l];
}
arr[l] = tempBase;
System.out.println(Arrays.toString(arr));
if(l == k) return arr[l];
if(l > k){
result = subKMinNumQuickSort(arr,lsave,l - 1,k);
}else {
result = subKMinNumQuickSort(arr,l + 1,rsave,k);
}
return result;
}
/**
* 7.选择排序，有点堆排的意思，思想一样，运用的数据结构不同
* 时间复杂度：O(n*n)
*/
public static void selectSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int minTemp = arr[i];
int minIndex = i;
for (int j = i + 1; j < len; j ++){
if(minTemp > arr[j]) {
minTemp = arr[j];
minIndex = j;
}
}
swap(arr,i,minIndex);
}
}
/**
* 8.基数排序：对每一个元素，先按个位排，再按十位排，以此到最大值的最高位
* 9.希尔排序:按间隔分组，每组逐渐包含更多元素，不断插入排序。总体上数据移动较少，复杂度优于O(n*n)
*/
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + Arrays.toString(data));
selectSort(data);
System.out.println("排序之后：\n" + Arrays.toString(data));
}
}
内容总结
以上是互联网集市为您收集整理的九种常见排序算法全部内容，希望文章能够帮你解决九种常见排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】