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

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

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

智能推荐

解决Matlab下mex不到 MinGW-w64 编译器问题_不说�的博客-程序员宝宝_matlab检测不到mingw

环境:win10+matlab2014b1.安装MinGW-w642.下载之后,设置环境变量文件资源管理器–&gt;属性–&gt;高级系统环境设置–&gt;环境变量(这里要设置两个地方)一个系统变量下path路径下添加 MinGW-W64的bin目录另一个是新建–&gt;变量名 NW_MINGW64_LOC 变量值是 安装TDM-GCC-64的路径3.在cmd下 输入 gcc...

程序员面试题精选100题(31)-从尾到头输出链表_linxhpku的博客-程序员宝宝

 http://zhedahht.blog.163.com/blog/static/2541117420079237185699/ 题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:struct ListNode{      int       m_nKey;      ListNode* m_pNext;};

从零开始学 Web 前端系列教程_前端队长Daotin的博客-程序员宝宝_从零开始学web前端教程

???? 开始吧,前端!从零开始学 Web 前端系列教程。前端小白零基础自学入门进阶图文教程。

C#Convert.ToInt32(decimal)方法-将十进制值转换为int_cumt30111的博客-程序员宝宝

C#Convert.ToInt32(decimal)方法 (C# Convert.ToInt32(decimal) Method)Convert.ToInt32(decimal) Method is used to convert a specific decimal value (that may contain a number with or without fractional par...

如何实现上拉加载和下拉刷新_elementui上拉加载_不秃头的小铭的博客-程序员宝宝

开源社区也有很多优秀的解决⽅案,如 iscroll 、 better-scroll 、 pulltorefresh.js 库等等 这些第三⽅库使⽤起来⾮常便捷。下拉刷新、上拉加载原理本身都很简单,真正复杂的是封装过程中,要考虑的兼容性、易⽤性、性能等 诸多细节。我们通过原⽣的⽅式实现⼀次上拉加载,下拉刷新,有助于对第三⽅库有更好的理解与使⽤。下拉刷新的本质是⻚⾯本身置于顶部时,⽤户下拉时需要触发的动作。最重要的是要理解在什么场景,什么时机下触发交互动作。上拉加载的本质是⻚⾯触底,或者快要触底时的动作。

盘点:中国“颜值+才华”的几位知名女程序员!如何看待女生当程序员?_一起学编程的博客-程序员宝宝

毫无疑问,世人对程序员行业普遍存在的误区:1.程序员都是男性。2.程序员都是邋里邋遢,不修边幅,整天就穿一套衣服,一年都不会换一双鞋子……其实,我们的阵营里也有很多女孩纸,她们人品、衣品各个一流!今天就为大家盘点中国“颜值+才华”的几位知名美女程序员!一、俞淑婷(清宵)清宵是阿里“飞天”技术部的资深开发工程师,在高手云集的飞天技术团队,除了努力、积极、细心、敢于担当、靠谱,这些技术人的优点之外,更重要的是,她还具备了男工程师们没有的独特标签:美丽、长腿。在那次阿里年会上,清宵也开启自己的“维密之

随便推点

HOJ多校联合练习 A. Ascending Rating_Sher杨的博客-程序员宝宝

 问题 A: Problem A. Ascending Rating时间限制: 5 Sec  内存限制: 512 MB提交: 18  解决: 6[提交] [状态] [讨论版] [命题人:admin]题目描述Before the start of contest, there are n ICPC contestants waiting in a long queue. They...

常用 Normalization 方法与PyTorch接口_海清河宴的博客-程序员宝宝_normalization pytorch

常用 Normalization 方法与PyTorch接口简介简介常用的Normalization方法主要有:Batch Normalization(BN,2015年)、Layer Normalization(LN,2016年)、Instance Normalization(IN,2017年)、Group Normalization(GN,2018年)。它们都是从激活函数的输入来考虑、做文章的...

ARQ(自动重传请求)协议_赵鹏翔的博客-程序员宝宝_arq自动请求重传协议

自动重传请求(Automatic Repeat-reQuest,ARQ)是OSI模型中数据链路层和传输层的错误纠正协议之一。它通过使用确认和超时这两个机制,在不可靠服务的基础上实现可靠的信息传输。如果发送方在发送后一段时间之内没有收到确认帧,它通常会重新发送。ARQ包括停止等待ARQ协议和连续ARQ协议。停止等待ARQ协议停止等待协议是为了实现可靠传输的,它的基本原理就是每发完一个分组就停止发送,等待对方确认(回复ACK)。如果过了一段时间(超时时间后),还是没有收到 ACK 确认,说明没有发送成功,需

程序员面试题精选100题(31)-从尾到头输出链表_linxhpku的博客-程序员宝宝

 http://zhedahht.blog.163.com/blog/static/2541117420079237185699/ 题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:struct ListNode{      int       m_nKey;      ListNode* m_pNext;};

PostgreSQL 数据去重大法_weixin_34344403的博客-程序员宝宝

标签PostgreSQL , 去重 , 单列去重 , 多列去重 , 行去重 , 多列混合去重 , varidict 参数 , 数组排序 , 数组元素重排背景去重的需求比较常见,去重也可以衍生出很多变种。例如1. 单列去重,很好理解,就是按某列去除重复记录。保留规则(例如保留最新的,保留最旧的,或者保留某个其他字段最大的)。2. 多列去重,按...

centos6.5安装php环境php apache mysql_aosu9037的博客-程序员宝宝

以下全部是root用户登录centos1.安装apache查看是否已经安装#rpm -qa httpd命令安装#yum install httpd -y设置开机启动chkconfig httpd on启动软件service httpd start此时浏览器输入服务器ip地址显示无法访问,因为没有设置服务器防火墙放行80端口。修改防火墙配置文件,加入80端口#v...

推荐文章

热门文章

相关标签