排序算法/sort 基本的排序算法
- 冒泡排序/Bubble Sort
- 插入排序 / Insertion Sort
- 归并排序/Merge Sort
- 快速排序/Quick Sort
- 拓扑排序/Topological Sort
- 堆排序/Heap Sort
- 桶排序/Bucket Sort
空间复杂度:O(1)
时间复杂度:O(n^2)
文章图片
publicvoid bubbleSort(int[] ary) {
//外层or循环表示轮数
for (int i=0;
iary[j+1]){
int tmp = ary[j];
ary[j]=ary[j+1];
ary[j+1] = tmp;
}
}
}
}String[] ary = {"tom","amy","jack","rose","张三","李四"};
//使用冒泡排序对String[]进行升序排列
for (int i=0;
i0){
String tmp = ary[j];
ary[j]= ary[j+1];
ary[j+1]=tmp;
}
}
}
System.out.println(Arrays.toString(ary));
插入排序 不断地将尚未排好序的数插入到已经排好序的部分。在插入排序中，经过每一轮的排序处理后，数组前端的数都是排好序的。
空间复杂度:O(1)
时间复杂度:O(n^2)
文章图片
void insertionSort(int[] nums) {
for (int i =1, j,current;
i < nums.length;
i++){
current = nums[i];
for ( j = i - 1;
j >= 0 && nums[j] > current;
j--){
nums[j +1] = nums[j];
}
nums[j + 1] = current;
}
}
归并排序 归并排序的核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。把数组从中间划分成两个子数组; 一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素;
空间复杂度:O(n)
时间复杂度:O(nlogn)
文章图片
/*归并排序的主体函数*/
void sort(int[] A， int lo, int hi) {
if (lo >= hi) return;
int mid = lo +(hi - lo)/ 2;
sort(A，lo， mid);
sort(A, mid + 1, hi);
merge(A,lo, mid, hi);
}
void merge(int[] nums, int lo， int mid， int hi) {
int[]copy = nums.clone();
int k = lo, i = lo， j = mid + 1;
while (k <= hi){
if (i > mid) {
nums[k++] = copy[j++];
}else if(j >hi) {
nums[k++] = copy[i++];
}else if (copy[j]快速排序/ Quick Sort 快速排序也采用了分治的思想;
把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组;
在分成较小和较大的两个子数组过程中，如何选定一个基准值尤为关键。
时间复杂度:O(n^2)
空间复杂度:O(Iogn)
文章图片
/*快速排序的主体函数*/
void sort(int[] nums,int lo，int hi){
if (lo >= hi) return;
int p = partition(nums， lo, hi);
sort(nums,lo，p - 1);
sort(nums, p + 1,hi);
}
int partition(int[] nums, int lo，int hi) {
swap(nums,randRange( lo,hi), hi);
int i，j;
for (i = lo， j = lo;
j【算法|算法之排序/sort】
推荐阅读
- 算法/数据结构|数据结构与算法_01_时间复杂度和空间复杂度
- 数据结构和算法|【大厂必会的数据结构和算法】01-稀疏数组和队列
- 数据结构初阶|【C语言 - 数据结构】树、二叉树（下篇）
- c++|C++八种排序算法万字详解
- 算法/数据结构|数据结构与算法_合集导航
- 如何在Java中向左或向右旋转数组（）
- 如何在Java中初始化和比较字符串（）
- 如何在Binary Search Tree中实现减小键或更改键（）
- 如何识别一种语言是否正常（）