排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含6422字,纯文字阅读大概需要10分钟。
内容图文
![排序算法](/upload/InfoBanner/zyjiaocheng/595/7fce91dfd4bf449ca1cbd72a2cd72e3c.jpg)
排序
0.复杂度
0.1 时间复杂度
语句执行的次数 数量级
0.2 空间复杂度
1.交换排序
1.1冒泡排序
/**
* 两层循环,相邻比较交换
*/
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
1.2 快速排序
public class QuickSort {
/**
* 快速排序:
*/
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
//中间值
int pivot = arr[left];
int l = left, r = right;
//从左往右,将比pivot大的放右边
while (l < r) {
//在pivot右边找到比pivot小的一个
while (l < r && pivot <= arr[r]) {
r--;
}
arr[l] = arr[r];
//在pivot左边找到比pivot大的一个
while (l < r && arr[l] <= pivot) {
l++;
}
arr[r] = arr[l];
}
arr[l] = pivot;//重合位
quickSort(arr, left, l);
quickSort(arr, l + 1, right);
}
}
public static void main(String[] args) {
int[] a = {2, 5, 3, 10, 2, 9, 8, 6, 7};
quickSort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
}
2.插入排序
2.1 直接插入
/**
* 将无序部分的首位依次与有序部分依次比较,同时交换位置,直到到达合适位置
*/
for (int i = 1; i < arr.length; i++) {
int num = arr[i];//记录要插入的数
int j;//标记移动位置
for (j = i - 1; j >= 0; j--) {
if (num < arr[j]) {
arr[j + 1] = arr[j];//原位置直接覆盖
} else {
break;
}
}
arr[j + 1] = num;//arr[j]放在最后空出的位置
}
2.2 希尔排序
public class ShellSort {
/**
* 希尔排序:依次跳跃式分组排序
*/
public static void shellSort1(int[] arr) {
//第一轮排序,gap为总长一半
int temp = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
/**
* 交换式:
*/
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
public static void shellSort2(int[] arr) {
/**
* 移位式
*/
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第gap个开始,组内进行插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
//将 arr[j] 插入到合适位置(组内往前)
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 4, 5, 0};
shellSort2(arr);
System.out.println(Arrays.toString(arr));
}
}
3.选择排序
3.1 简单选择
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
3.2 堆排序
4.其他排序
4.1 归并排序
public class MergeSort {
/**
* 归并排序
*/
public static void merge(int[] arr, int low, int mid, int high) {
//临时数组
int[] temp = new int[high - low + 1];
int index = 0;
//记录两段的下标
int i = low, j = mid + 1;
while (i <= mid && j <= high) {
//将两段合并排序存入temp
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
//可能有剩余
while (j <= high) {
temp[index++] = arr[j++];
}
while (i <= mid) {
temp[index++] = arr[i++];
}
?
for (int k = 0; k < temp.length; k++) {
arr[k + low] = temp[k];
}
}
//排序入口
public static void mergeSort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
//递归返回
if (low >= high) return;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
?
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random()*100);
}
mergeSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
4.2 基数排序
public class RadixSort {
public static void radixSort(int[] arr) {
//找到最大元素
int max = Integer.MIN_VALUE;
for (int i : arr) {
if (i > max) {
max = i;
}
}
//临时存放
int maxLength = (max + "").length();
int[][] temp = new int[10][arr.length];
int[] counts = new int[10];
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//根据第i位数字进行分组
int ys = arr[j] / n % 10;
temp[ys][counts[ys]] = arr[j];
counts[ys]++;
}
//将排序后的放回原数组
int index = 0;
for (int j = 0; j < counts.length; j++) {
if (counts[j] != 0) {
for (int k = 0; k < counts[j]; k++) {
arr[index++] = temp[j][k];
}
counts[j] = 0;//重置分组
}
}
}
}
?
public static void main(String[] args) {
int[] arr = {123,33,66,45,186,3135,22,335,666,159,987};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
}
5.排序算法总结
5.1 复杂度
排序方法 | 平均时间 | 最坏时间 | 辅助空间 | 稳定性 | |
---|---|---|---|---|---|
冒泡排序 | O(n2) | O(n^2) | O(1) | 稳定 | |
选择排序 | O(n2) | O(n2) | O(1) | 不稳定 | |
插入排序 | O(n2) | O(n2) | O(1) | 稳定 | |
快速排序 | O(nlogn) | O(n2) | O(logn) | 不稳定 | |
堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
希尔排序 | O(nlogn2) = O(n1.3) | O(n2) | O(n) | 不稳定 | |
计数排序 | O(n + k) | O(n + k) | O(k) | 稳定 | |
桶排序 | O(n + k) | O(n2) | O(n) | 稳定 |
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。