排序算法总结
排序算法比较
https://www.cnblogs.com/bjwu/articles/10006419.html
冒泡排序
/**冒泡排序
* 第一次比较0~N-1位 将最大值沉底
* 第二次比较0~N-2位 将最大值沉底
* ......
* 第N-1次比较0~1位 将最大值沉底（在0~1中沉底）
* 时间复杂度：O(n^2)
*/
public static void sort(int[] nums){
if(nums == null || nums.length < 2){
return;
}
for(int end = nums.length-1; end > 0; end--){
for(int j = 0; j < end; j++){
if(nums[j] > nums[j+1]){
swap(nums,j,j+1);
}
}
}
}
public static void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}插入排序
/** 插入排序
* 0~end-1 位置的数都有序
* 每次考察end位置的数应该插在哪里
* 如果前面的数比end位置数大则交换
*
* 插入选择时间复杂度和数据样本无关
* 插入排序 有序 O(n) 逆序O(n^2)
* 时间复杂度按最差的算
* 所以插入排序的时间复杂度是O(n^2)
*/
public static void sort(int[] nums){
for(int end = 1; end < nums.length; end++){
for(int i = end-1; i >= 0; i--){//与前面有序部分比较是否能够交换
if(nums[i] > nums[i+1]){
swap(nums,i,i+1);
}
}
}
}
public static void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}选择排序
/**选择排序
* 第一次比较 0~N-1 找到最小值的位置和0交换
* 第二次比较 1~N-2 找到最小值的位置和1交换
* ......
* 第N-1次比较 N-2~N 找到最小值的位置和N-2交换
* 时间复杂度：O(N^2)
*/
public static void sort(int[] nums){
if(nums == null || nums.length < 2){
return;
}
for(int start = 0; start < nums.length; start++){
int minIndex = start;
for(int i = start; i < nums.length; i++){
minIndex = nums[i] < nums[minIndex]? i:minIndex;
}
swap(nums, minIndex, start);
}
}
public static void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}快排
public static void quickSort(int [] nums, int left, int right){
if (nums == null || nums.length < 2) {
return;
}
if(left < right){
//随机选一个位置和最后一个数字交换
swap(nums, left+(int)Math.random()*(right-left+1), right);
int[] p = partition(nums, left, right);//等于区域的左边界和右边界
quickSort(nums, left, p[0]-1); // 小于区域递归
quickSort(nums, p[1]+1, right); // 大于区域递归
}
}
public static int[] partition(int[] nums, int left, int right){
int smaller = left - 1; // 小于区域的右边界
int bigger = right; // 大于区域的左边界
while(left < bigger){
int target = nums[right];
if(nums[left] > target){
swap(nums,left,bigger-1);
bigger--;
}else if(nums[left] < target){
swap(nums,left,smaller+1);
smaller++;
left++;
}else {
left++;
}
}
swap(nums, bigger, right);
return new int[]{smaller+1,bigger};
}
public static void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}归并排序
/**归并排序
* 左边排序 右边排序
* 外排整体排序 辅助数组
* 左边有序数组和右边有序数组谁小谁加入辅助数组
* T(N) = 2T(N/2) + O(N)
* log2(2) = 1 = d -->
* 时间复杂度为 O(N*logN)
*/
public static void mergeSort(int[] nums){
if(nums ==null || nums.length < 2){
return;
}
sortProcess(nums, 0, nums.length-1);
}
public static void sortProcess(int[] nums, int left, int right){
if(left == right){//结束递归条件 这个范围只有一个数
return;
}
int mid = left + (right - left)/2;
sortProcess(nums,left,mid);//左边有序 T(N/2)
sortProcess(nums,mid+1,right);//右边有序 T(N/2)
merge(nums, left, mid, right);//外排序 O(N)
}
public static void merge(int[] nums, int left, int mid, int right){
int[] help = new int[right-left+1];//left到right有多少个数
int i = 0;//指向help
int p1 = left;//指向左侧数组第一个数
int p2 = mid+1;//指向右侧数组第一个数
while(p1 <= mid && p2 <= right){//有一个数组读完了就退出循环
//哪边小哪边的p指向的元素加入help 加入之后移动p指针
help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
}
//只有一个越界 把剩余的数组一次性添加进help
while(p2 <= right){
help[i++] = nums[p2++];
}
while(p1 <= mid){
help[i++] = nums[p1++];
}
//将help中的依次覆盖nums
for(int j = 0; j < help.length; j++){
nums[left+j] = help[j];
}
}逆序和 & 最小和都可以用归并排序的思路来解
逆序对
/**
* 逆序对和最小和求解思路的区别
*
* 【最小和】是优先找小值
* [1,1,2] [2,3,4]
* 优先在左侧数组找到小值后 右边剩下的就都比该值要大了 从左向右遍历
* 例如：对于左边第一个元素1 右边第一个元素2及2之后的所有元素都对1有一个小和
* smallsum += 1 * (right-p2+1)
* 即 如果左小于右 累加
*
* 【逆序对】要求是左侧元素大于右侧
* 优先在左侧找大值 对于升序排序 大值在最右边 应该从右向左遍历
* [1,1,5] [1,3,4]
* 例如：对于左边最后一个元素5 大于右边最后一个元素4 则5可以和4及4之前的所有元素形成一个逆序对
* [5,1][5,3][5,4]
* count += right-(mid+1)+1 5 - 3 + 1 = 3 个
* 即 如果左大于右 累加
*/
public class ReversePair {
private static int count;
private static List<int[]> list = new ArrayList<>();
public static void mergeSort(int[] nums){
if(nums ==null || nums.length < 2){
return;
}
sortProcess(nums, 0, nums.length-1);
}
public static void sortProcess(int[] nums, int left, int right){
if(left == right){//结束递归条件 这个范围只有一个数
return;
}
int mid = left + (right - left)/2;
sortProcess(nums,left,mid);//左边有序 T(N/2)
sortProcess(nums,mid+1,right);//右边有序 T(N/2)
merge(nums, left, mid, right);//外排序 O(N)
}
public static void merge(int[] nums, int left, int mid, int right){
int[] helper = new int[right -left + 1];
int p = right - left;
int rightBegin = mid + 1;
while(left <= mid && rightBegin <= right){
if(nums[mid] > nums[right]){
count += (right - rightBegin)+1;
for(int k = right; k >= rightBegin; k--){
list.add(new int[] {nums[mid],nums[k]});
}
helper[p--] = nums[mid--];
}else{
helper[p--] = nums[right--];
}
}
while(left <= mid){
helper[p--] = nums[mid--];
}
while(right >= rightBegin){
helper[p--] = nums[right--];
}
for(int help:helper){
nums[left++] = help;
}
}
public static void main(String[] args) {
int[] nums = {3,5,4,2,1};
mergeSort(nums);
System.out.println(Arrays.toString(nums));
System.out.println(count);
for(int[] pair: list){
System.out.println(Arrays.toString(pair));
}
}
}最小和
public class SmallSum {
public static int smallSum(int[] arr){
if(arr == null|| arr.length < 2){
return 0;
}
return mergeSort(arr,0,arr.length-1);
}
/**
* 计算left ~ right范围内有多少小和
*/
public static int mergeSort(int[] arr, int left, int right){
if(left == right){
return 0;
}
int mid = left + ((right - left) >> 1); //右移1位 等于 除以2
//mid = left + (right - left)/2; 防止溢出
return mergeSort(arr, left, mid)+//左边排序产生的小和
mergeSort(arr, mid+1, right)+//右边排序产生的小和
merge(arr, left, mid, right);//最后合并产生的小和
}
public static int merge(int[] arr, int left, int mid, int right){
int[] help = new int[right-left+1];//准备一个临时数组
// 长度和传进来的arr一样 是原arr的一部分 用left和right划分出来的一部分
int i = 0;
int p1= left;
int p2 = mid+1;
int res = 0;//计算小和
while(p1 <= mid && p2 <= right){
//关键在这里：
// 每一次比较可以知道比当前值更大的值有几个，这个较小的当前值就需要累加多少次。
//如果左边小于右边，那就有(r - p2 + 1)个arr[p1]元素的和是最小和，进行累加。
//p2后面的个数 * p1指向的数
res += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
}
while(p1 <= mid){
help[i++] = arr[p1++];
}
while (p2 <= right){
help[i++] = arr[p2++];
}
for(i = 0; i < help.length; i++){
arr[left+i] = help[i];
}
return res;
}
public static void main(String[] args) {
int[] nums = {1,3,4,2,5};
int i = smallSum(nums);
System.out.println(i);
}
}堆排序
/**
* HeapSort展示了heapinsert和heapify的两个过程
* 时间复杂度是O(NlogN)
* 实际上可以只用heapify
* 用heapify代替heapinsert从后向前heapify
* 原来的heapinsert是O(NlogN) heapify时间复杂度是O(N) 可以稍微快一点
* 但最后的时间复杂度还是O(NlogN) 因为后面的操作还是O(NlogN)
*/
public class HeapSort {
//堆化【调整堆】 某个数在index值 能否往下移动
public static void heapify(int[] nums, int index, int heapSize){
//index是初始的父节点
int left = index * 2 + 1; //左孩子
while(left < heapSize){//下方还有孩子时 没有越界
int largest = left;
if(left + 1 < heapSize) {//右孩子存在 没有越界
//左右两孩子PK
largest = nums[left]>nums[left+1]?left:left+1;
}
//较大孩子和父亲PK
largest = nums[index]>nums[largest]?index:largest;
//父亲最大不交换
if(largest == index){
break;
}
//父亲和较大孩子交换
swap(nums, largest, index);
//下一个比较的数 新父亲
index = largest;
//交换后的新的左孩子
left = index * 2 + 1;
}
}
/**
* 无序数组 相当于依次插入大根堆 heapinsert
* 得到大根堆后
* 每次让数组第一个元素（最大值）和最后一个元素交换
* 交换后heapsize--，调整堆heapify为大根堆
* 最后heapsize == 0 数组有序
*/
public static void heapSort(int[] nums){
if(nums == null || nums.length < 2){
return;
}
for (int i = nums.length-1; i >= 0; i--) {
heapify(nums,i,nums.length);
}
int heapSize = nums.length;
swap(nums,0,--heapSize);//先交换
while(heapSize > 0){
heapify(nums,0,heapSize);//再堆化
swap(nums,0,--heapSize);//继续交换
}
}
public static void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public static void main(String[] args) {
int[] nums = {2,3,1,4,4,3,3,4,5,1};
heapSort(nums);
System.out.println(Arrays.toString(nums));
}
}适用于求基本有序的数列
* 已知一个几乎有序的数组，几乎有序是指，
* 如果把数组排好顺序的话，每个元素移动的距离可以不超过K
* 可以用堆排序来解决这个问题
*
* 思路：
* 1.建立有K个元素的小顶堆，然后取出顶上元素
* 2.堆顶用没有建堆的下一元素替代，重新建堆
* 3.反复调用，完成排序，此算法因为每个元素移动都在k以内，所以时间复杂度为O(NlogK)
*/
public class KHeapSort {
public static void kHeapSort(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index= 0;
//k个值加入堆
for(; index <= Math.min(k, nums.length); index++){
heap.add(nums[index]);
}
int i = 0;
//从index的下一个位置开始遍历 也就是k+1
for(; index < nums.length; i++,index++){
heap.add(nums[index]);//加一个 heapsize+1
nums[i] = heap.poll();//弹一个 heapsize-1
}
while (!heap.isEmpty()){
nums[i++] = heap.poll();
}
}
public static void main(String[] args) {
int [] nums ={3,2,7,1,8,6,4,5,12,10,15,9,13,14,11,20,16,17,18,19};
kHeapSort(nums,7);
System.out.println(Arrays.toString(nums));
}
}基数排序
public class RadixSort {
/**
* 统计最大值有多少位
*/
public static int maxbits(int[] nums){
int max = nums[0];
for(int i = 0; i < nums.length; i++){
max = Math.max(nums[i], max);
}
int count = 0;
while(max > 0){
max /= 10;
count++;
}
return count;
}
/**
* 获取倒数第i位的数字 i=1 取出个位
*/
public static int getDigit(int num,int i){
while(i > 1){
num /= 10;
i--;
}
return num%10;
}
/**
* 基数排序
*/
public static void radixSort(int[] arr){
int digit = maxbits(arr);
//基数 10
final int radix = 10;
//给每个数准备一个桶
int[] buckets = new int[arr.length];
//有多少位 就要出桶进桶几次
for(int d = 1; d <= digit; d++){
//计数器 等于count的有几个
int[] count = new int[radix];
for(int i = 0; i < arr.length; i++){
int j = getDigit(arr[i],d);
count[j]++;
}
//将count变为前缀和 小于等于count的有几个
for(int i = 1; i < radix; i++){
count[i] += count[i-1];
}
System.out.println(Arrays.toString(count));
//数组从右向左遍历 入桶
for(int i = arr.length-1; i >=0; i--){
int j = getDigit(arr[i],d);
buckets[count[j]-1] = arr[i];
count[j]--;
}
//当前位数出桶
for(int i = 0; i < arr.length; i++) {
arr[i] = buckets[i];
}
}
}
public static void main(String[] args) {
int[] nums = {123,423,19,32,321,1200};
radixSort(nums);
System.out.println(Arrays.toString(nums));
}
} 相关推荐
Oudasheng 2020-05-29
shawsun 2020-01-12
YUAN 2019-11-17
lixiaotao 2019-11-15
风和日丽 2019-11-03
HeavyIndustry 2014-11-25
风吹夏天 2014-04-07
WalkMoreSlowly 2012-10-25
算法改变人生 2019-06-27
代码之神 2019-06-27
代码之神 2019-06-25
韦一笑 2011-04-20
hang0 2011-04-20
WindChaser 2011-04-20
hugebawu 2011-04-20
RememberMePlease 2011-04-20
MrA 2011-04-20