排序详解。_我顶得了的博客-程序员宝宝_\排序

技术标签: 算法  排序算法  数据结构  

1. 冒泡排序:

思想:将元素前后比较,大的放到后面去,最终每轮循环过后都可以将当前区间的最大元素放到最后面(每轮循环过后区间大小减一)

public static void bubbleSortLowBetter(int[] array){
    
	int n = array.length;
	//循环n - 1次
	for(int i = 0;i < n - 1;i++){
    
	//前后交换位置,每循环一次都可以把当前无序数组最大的元素放在最后面去
	///所以每次循环次数都减i
		for(int j = 0; j < n - i - 1; j++){
    
		//如果前面的大于后面的,则将其交换位置
			if(array[j] > array[j + 1]){
    
				int temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	} 
}

2. 插入排序:

2.1 直接插入排序:

思想:
默认第一个元素为有序数组,后面的为无序数组。
首先用value将要排序的数字保存起来,将无序数组的第一个元素与有序数组从后向前一一比较,因为已经提前用value保存了无序数组的第一个(也就是有序数组最后一个的下一个))所以如果value小于有序数组元素,有序数组元素可以直接依次向后推移(前面的覆盖后面的,为value的插入让出位置)。当value大于数组中的元素时,跳出循环将value插到那个元素的后面(之前那个位置的元素后面得元素已经依次向后推移到下一个位置了)

 public static void insertSort(int[] array){
    

 	int n = array.length;
 	//外层循环是将所有元素遍历一遍
 	//内层循环是给当前元素找到位置
 	//两层循环过后所有元素都找到了正确的位置
 	for(int i = 1;i < n;i++){
    
 		//已排序集合的最后一个元素下标
		int j = i - 1;
		//待排序集合的第一个元素
		int value = array[i];
		//将待排序元素与已经排好序的数组(从最后一个元素开始,每次j--向前推进)作比较,
		//如果已经排好的元素大于待排序的元素,则将其向后移一位(array[j + 1] = array[j];)
		//直到遇到小于待排序的元素,或者到头,则将需要排序的元素其插入到这个小于待排序的元素后方。
		for(;j >= 0;j--){
    
			if(array[j] > value){
    
				array[j + 1] = array[j];
			}else{
    
				break;
			}
			//假如此时已经到了最后一步,j--后,比较array[j]与value的大小,发现value不小于array[j]
			//则将value放在array[j]的后面,也就是array[j + 1] = value;
			//并且此时的array[j + 1]的值已经在上一轮的循环中依次向后推移了,所以不必担心,array[j]后面的值没被保存
		}					
		array[j + 1] = value;	
	}
 }

2.2 折半插入排序(二分查找排序):

思想:将无序集合的第一个元素i与有序集合的中间元素mid相比较

  1. 如果比中间元素大,那么一定比中间数组前面的元素要大,则可以以mid + 1作为新的分区起始位置。
  2. 如果比中间元素小,那么也就比中间元素后面的小,则以mid - 1作为新的数分区起始位置。
  3. 直到Low和High的前后位置发生变化,此时High + 1的位置为新的元素插入点

当数组无序的时候这种方法效率更高,但是当数组近乎有序的时候,不如直接插入排序从前向后比较。

public static void binaryInsertSort(int[] array){
    
      int low,high,mid,temp = 0;
      int n = array.length;
      //此循环是将无序数组的元素与有序数组的元素比较,找到无序数组元素应该放在有序数组的哪
      for(int i = 1; i < n; i++){
    
          //有序集合的第一个元素
          low = 0;
          //有序集合的最后一个元素(无序集合第一个元素的上一个元素)
          high = i - 1;
          //无序集合的第一个元素(正在排序的元素)
          temp = array[i];
          //当low > high的时候,将新的元素插到high的后面(high + 1)
          while(low <= high){
    
              //有序集合的中间元素
              mid = (high + low)/2;
              if(array[mid] > temp){
    
                  low  = mid + 1;
              }else{
    
                  high = mid - 1;
              }
          }
          //此时j是由后向前推进,所以只需 > high即可,这样会在high前停下,如果 = high则会跨过high。
          //由于循环的最后一步 j--,所以此处为 j + 1。
          int j = i - 1;
          for(;j > high; j--){
    
              array[j + 1] = array[j];
          }
          array[j  + 1] = temp;
      }
  }

2.3 希尔排序(缩小增量排序):

因为直接插入排序对于近乎有序的序列效率较高。
所以希尔排序是将待排序的的序列分成若干小的序列(以步长进行分组,一般以数组的一半开始,每次循环除2)进行直接插入排序,最后再将基本有序的整体序列(也就是步长为1的序列)进行一次直接插入排序。

public static void shellSort(int[] array){
    
	int n = array.length;
	int step = n/2;
	//当步长为1的循环结束,序列也就完全有序了,此时跳出循环
	while(step >= 1){
    
		//外层循环,遍历每一个元素
		for(i = step;i < n;i++){
    
		//value保存无序数组的第一个元素,因为待会会被覆盖
		int value = array[i];
		//有序数组的第一个元素
		int j = i - step;	
		//内层循环,给当前元素找到合适的位置
			for(;j >= 0;j -= step){
    
				if(array[j] > array[j + step]){
    
					//如果有序数组的元素大于无序数组元素,无序数组元素向后推移
					array[j + step] = array[j];      
				}else{
    
					break;
				}
			}
			array[j + step] = value;
		}
		step = step/2;
	}
}

3.简单选择排序

思想:
每次都找到当前无序数组中最小(最大),放到无序数组的最前面(最后面),也就是与最前面(最后面)的元素交换位置。

 public static void selectionSort(int[] array) {
    
 	int n = array.length;
 	//外层i可以理解为有序数组最后一个的下标
 	for(int i = 0;i < n - 1;i++){
    
 		int minIndex = i;
 		//内层j可以认为是无序数组的第一个下标
 		//将无序数组从前向后遍历,如果其中有小于array[i]的那么就找到其中最小的
 		//如果没有,则array[i]保持原位,i++,继续比较后面的元素
		for(int j = i + 1;j < n;j++){
    
			if(array[minIndex] > array[j]){
    
				minIndex = j;
		}
		if(array[i] != array[minIndex]){
    
			int temp = array[i];
			array[i] = array[minIndex];
			array[minIndex] = temp;
		}
	}
 }

4. 归并排序:

思想:
归并排序算法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
注:当拆分到最后一步时,每个数组中只有一个元素,那么此时可以认为数组都是有序的。


/*
拆分数组
p为数组的开始位置,r为数组结束位置
*/
private static void mergeSortIntern(int[] array,int p,int r) {
    
	//终止条件
	if(p > r){
    
		return;
	}
	int mid = (p + r)/2;
	//将数组左半部分拆分
	mergeSortIntern(array,p,mid);
	//将数组右半部分拆分
	mergeSortIntern(array,mid + 1,r);
	//将数组合并
	merge(array,p,mid,r);
}

/*
合并数组
p为数组起始位置
mid为数组中间位置
r为数组终止位置
*/
private static void merge(int[] array,int p,int mid,int r) {
    
	/*
	i、j、k可以理解为三个指针
	i指向左数组的第一个位置
	j指向右数组的第一个位置
	k指缓存数组的第一个位置
	将左数组与右数组的元素从头开始比大小,哪边小将哪边元素加入temp数组
	然后k指针向后移动一位,同时那个i或者j也向后移动一位
	直到i或者j达到数组边缘,此时循环结束
	*/
	int i = p;
	int j = mid + 1;
	int k = 0;
	int temp = new int[r - p + 1];
	while(i <= mid && j <= r){
    
		if(array[i] < array[j]){
    
			temp[k++] = array[i++];
			/*
			temp[k] = array[i];
			k++;
			i++;
			*/
		}else{
    
			temp[k++] = array[j++];
		}
	}
	
	/*
	判断左右数组中还有哪个数组剩有元素,将剩余元素加入temp数组中
	首先默认是左数组中还剩元素,之后判断如果j指针没有指到数组最后一位的下一位
	则剩下的是右数组,给start与end重新赋值
	*/
	int start = i;
	int end = mid;
	if(j <=   r){
    
		int strat = j;
		int end = r;
	}
	while(start < end){
    
		temp[k++] = array[start++];
	}
	
	//将temp中的数据写回原数组(用正确顺序的数组覆盖原数组)
	for(i = 0; i < r - p; i++){
    
		array[p + i] = temp[i];
	}
}

5. 快速排序

挖坑:

public class ex2 {
    
	//一个简单的测试用例
    public static void main(String[] args) {
    
        int[] a = new int[]{
    1,6,7,8,91,3,4,6,52,87,2,6,9};
        quickSort(a,0,a.length -1);
        for (int i:a
             ) {
    
            System.out.println(i);
        }
    }

    public static int p(int[] a,int l,int h) {
    
        int temp = a[l];//基准值
        while(l < h){
    
            //找到比基准值小的
            while((l < h) && a[h] >= temp){
    
                h--;
            }
            /*当跳出while循环只有两种情况:
              1.两个指针相遇了
              2.找到了比temp小的值
            */
            if(l == h){
    
                break;
            }else{
    
                a[l] = a[h];
            }
            //找到比基准值大的
            while((l < h) && temp > a[l]){
    
                l++;
            }
            if(l == h){
    
                break;
            }else{
    
                a[h] = a[l];
            }
        }
        //此时l == p
        a[l] = temp;
        return l;
    }

    public static void quick(int[] a,int low,int high) {
    
        if (low == high){
    
            return;
        }
        int par = p(a,low,high);
        //递归左边————>前提是左边有两个数据以上
        if (par > low + 1){
    
            quick(a,low,par -1);
        }
        //递归右边————>前提是保证右边有两个数据以上
        if (par < high -1){
    
            quick(a,par + 1,high);
        }
    }

    public static void quickSort(int[] a,int l,int h) {
    
        quick(a,l,h);
    }
}

左右指针:

public int[] MySort (int[] arr) {
    
        QuickSort(arr,0,arr.length - 1);
        return arr;
    }

    public void QuickSort(int[] input, int l, int r){
    
        //i,j记录数组左右端点
        int i = l;
        int j = r;
        //以数组第一个为基准值
        int v = input[l];
        while(i < j) {
    
            //找到右半边比基准值小的
            while (i < j && input[r] >= v) {
    
                i--;
            }
            //找到左半边比基准值大的
            while (i < j && input[l] <= v) {
    
                j++;
            }
            //交换
            swap(input,l,i);
        }
        //将基准值放入正确位置
        swap(input,l,i);
        //当基准值左边数组长度大于1再排序
        if (i - 1 > l){
    
            QuickSort(input,i,l - 1);
        }
        //当基准值右边数组长度大于1再排序
        if (j + 1 < r){
    
            QuickSort(input,l + 1,j);
        }
    }

    public void swap(int[] input,int a, int b){
    
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }

堆排序


import java.util.*;

/**
 * @author fengweibo
 * @version 1.0
 * @date 2021/10/27 20:26
 */

import java.util.*;


public class Solution {
    
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
    
        heapSort(arr);
        return arr;
    }

    public  void heapfiy(int[] tree, int n ,int i){
    
        if (i >= n) {
    
            return;
        }
        int max = i;
        int l = i * 2 + 1;
        int r = i * 2 + 2;
        if (l < n && tree[l] > tree[max]){
    
            max = l;
        }
        if (r < n && tree[r] > tree[max]){
    
            max = r;
        }
        if (max != i){
    
            swap(tree,max,i);
            heapfiy(tree,n,max);
        }

    }

    public  void swap(int[] tree,int i, int j){
    
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }

    //buildheap 建立稳定堆
    public  void buildHeap(int[] tree,int n){
    
        int i = (n-1)/2;
        for (int j = i; j >= 0; j--) {
    
            heapfiy(tree,n,j);
        }
    }


    //循环交换第一个元素与最后一个元素
    public  void heapSort(int[] tree){
    
        int n = tree.length;
        buildHeap(tree,n);
        for (int i = n - 1; i >= 0; i--) {
    
            swap(tree,0,i);
            heapfiy(tree,i,0);
        }
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38534524/article/details/96738989

智能推荐

安装rpm时报错:Header V3 RSA/SHA256 Signature, key ID fd431d51: NOKEY error: Failed dependencies:_pengpengfly_jhp的博客-程序员宝宝

[[email protected] Packages]# find ./ -name "*openmotif*"./openmotif-2.3.3-4.el6.i686.rpm./openmotif-2.3.3-4.el6.x86_64.rpm./openmotif-devel-2.3.3-4.el6.x86_64.rpm./openmotif-devel-2.3.3-4.el6.i686.rp

漂亮的 Checkbox and Radio (jQuery)_qqzeng-ip的博客-程序员宝宝

HTML:&lt;!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"&gt;&lt;html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" la...

哪种编程语言最吃香?_程曦2014的博客-程序员宝宝_程序员哪个语言最吃香

每年的3、4月份是招聘和找工作的高峰期,在这波大潮中也不乏程序员的身影。但是目前各种编程语言和技术层出不穷,而作为一个合格的程序员,至少掌握了一种语言,但这是否就是企业所需要的呢?  我们可以从Indeed中一探究竟。Indeed是全球最大的招聘求职网站,每月拥有1亿独立用户,Indeed的服务跨越50个国家,支持26种语言,覆盖了产生全球94%GDP的区域。  在所有的编程语言和技术中,

c语言 讲小写字母转换成大写_jor笛声的博客-程序员宝宝_c语言小写字母输出大写字母

#include&lt;iostream&gt;using namespace std;int main(){ char a; //定义char型的变量 scanf("%c",&amp;a); //键盘读入char型的小写字母 a=a-32; //让char型变量 - 数字32 printf("%c",a); //输出新的char型变量就得到大写的字母 return 0;}...

<mvc:annotation-driven />有什么作用_OkYang!的博客-程序员宝宝

当配置了mvc:annotation-driven/后,Spring就知道了我们启用注解驱动。然后Spring通过context:component-scan/标签的配置,会自动为我们将扫描到的@Component,@Controller,@Service,@Repository等注解标记的组件注册到工厂中,来处理我们的请求。...

算法设计模式之贪婪法_阿兵-AI医疗的博客-程序员宝宝_贪婪法

贪婪法贪婪法(greedy algorithm),又称贪心算法,是寻找最优解问题的常用方法。这种方法模式一般将求解过程分成若干个步骤,在每个步骤都应用贪心原则,选择当前状态下最好的或最优的选择(局部最有利的选择),并以此希望最后堆叠的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择,不从整体上考虑其他各种可能的情况。贪婪法和动态规划法以及分治法一样,都需要对...

随便推点

设置鼠标移进后以及鼠标点击后的JButton的背景图片_AlstonWilliams的博客-程序员宝宝

有两种方式实现,第一种是直接采用JButton自带的方法,推荐使用这种方式,因为代码少,具体代码如下: enter.setRolloverIcon(new ImageIcon("E:\\javaSE代码\\TimeManager\\asset\\buttonmousein.jpg"));//设置鼠标进来之后JButton的背景图片 enter.setPressedIcon(new Image

Lua 设置table为只读属性_少侠Smile丶的博客-程序员宝宝_lua table只读

原文大佬链接:http://www.cnblogs.com/vanishfan/p/6909153.html下面写一下自己能够理解的想法和思路:自己重新写了一遍,并添加注释

kubelet配置cni插件_第四步:树莓派Kubernetes集群安装_weixin_39967812的博客-程序员宝宝

4. Kubernetes集群安装4.1 master节点部署4.1.1 提前下载所需镜像看一下kubernetes v1.15.1需要哪些镜像:$ kubeadm config images list --kubernetes-version=v1.15.1k8s.gcr.io/kube-apiserver:v1.15.1k8s.gcr.io/kube-controller-manager:v1...

房价预测问题——神经网络的TensorFlow实现_蜡笔新小的博客-程序员宝宝_tensorflow 神经网络 r2

房价预测问题的tensorflow库直接实现,本来想输出r2,但是不太清楚怎么使用tensorflow直接输出r2,所以就用了lossimport tensorflow as tftf = tf.compat.v1tf.disable_v2_behavior()from sklearn.datasets import fetch_california_housingfrom sklearn.model_selection import train_test_splitfrom sklear.

C# 异步Task编程模型实战技巧手册_跟着阿笨一起玩NET的博客-程序员宝宝

一、课程介绍本次分享课程属于《C#高级编程实战技能开发宝典课程系列》中的第一部分,阿笨后续会计划将实际项目中的一些比较实用的关于C#高级编程的技巧分享出来给大家进行学习,不断的收集、整理和完善此系列课程!本高级系列课程适合人群如下:1、有一定的NET开发基础并对多线程技术有一定了解和认识。2、喜欢阿笨的干货分享课程的童鞋们。希望大家在选择阿笨的C#高级编程实战技能开发宝典课程系列的时候...

python课后答案第七周_MOOC《Python语言程序设计》第7周练习题_MFKc的博客-程序员宝宝

练习1:文件行数描述打印输出附件文件的有效行数,注意:空行不计算为有效行数。‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬输入输出示例这是仅给出输出格式样例,不是结果。‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‪‬‪‬‮...