十种排序算法理解(前五)

硅谷探秘者 4429 0 0

十种排序算法理解(前五)

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。

算法描述:

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

  • 针对所有的元素重复以上的步骤,除了最后一个;

  • 重复步骤1~3,直到排序完成。

maopao_.gif

代码

package sort.bubbling;
/**
 * 冒泡排序
 * @author LENOVO
 */
public class Bubbling {
	public static void main(String[] args) {
		int a[]= {2,1,3,9,5,6,4,7,8};
		for(int i=0;i<a.length;i++)
			for(int j=i+1;j<a.length;j++)
				if(a[i]>a[j]) {
					a[i]=a[i]+a[j];
					a[j]=a[i]-a[j];
					a[i]=a[i]-a[j];
				}
		for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
	}
}


2.选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 

算法描述 

  • 初始状态:无序区为R[1..n],有序区为空;

  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;

  • n-1趟结束,数组有序化了。

xuanze_.gif

代码

package sort.chose;
/**
 * 选择排序
 * @author LENOVO
 */
public class Chose {
	public static void main(String[] args) {
		int a[]= {2,1,3,9,5,6,4,7,8},index=-1,step;
		for(int i=0;i<a.length;i++) {
			step=a[i];
			for(int j=i+1;j<a.length;j++)
				if(step>a[j]) {
					step=a[index=j];
				}
			if(index!=-1) {
				a[i]=a[i]+a[index];
				a[index]=a[i]-a[index];
				a[i]=a[i]-a[index];
			}
			index=-1;
		}
		for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
	}
}


3.插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述

  • 从第一个元素开始,该元素可以认为已经被排序;

  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;

  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;

  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

  • 将新元素插入到该位置后;

  • 重复步骤2~5。

charu.gif

代码

package sort.insert;
/**
 * 插入排序
 * @author LENOVO
 */
public class Insert {
	public static void main(String[] args) {
		int a[]= {2,1,3,9,5,6,4,7,8},index, current;
	    for (int i = 1; i < a.length; i++) {
	        index = i - 1;
	        current = a[i];
	        while (index >= 0 && a[index] > current) {
	            a[index + 1] = a[index];
	            index--;
	        }
	        a[index + 1] = current;
	    }
	    for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
	}
}


4.希尔排序

希尔(Shell)排序又称为缩小增量排序,它是一种插入排序。它是直接插入排序算法的一种威力加强版。

算法描述

  • 把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。
    随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

1546350942124009654.png

代码:

package sort.shell;
/***
 * 希尔排序
 * @author LENOVO
 */
public class Shell {
	public static void main(String[] args) {
		int a[]= {4,5,6,1,2,3,7,8,9,0},increment =a.length,temp=0,j;
	    do {
	        increment = (int) Math.ceil((double)(increment)/3l);//每次减小增量,直到increment = 1
	        for (int i =increment; i < a.length; ++i)//对每个划分进行直接插入排序
	            if (a[i - increment] > a[i]) {
	                temp = a[i];
	                j= i - increment;
	                do {    //移动元素并寻找位置
	                    a[j + increment] = a[j];
	                    j -= increment;
	                } while (j >= 0 && a[j] > temp);
	                a[j + increment] = temp;  //插入元素
	            }
	    } while (increment > 1);
	    
	    for(int i=0;i<a.length;i++)
			System.out.print(a[i] + " ");
	}
}


5.归并排序:

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;

  • 对这两个子序列分别采用归并排序;

  • 将两个排序好的子序列合并成一个最终的排序序列。

QQ截图20190101220050.png

代码:

package sort.merge;

/**
 * 归并排序
 * @author LENOVO
 */
public class Merge{
	private static int[] result;
	private static int[] arr;
	static int s=0;//标记变量
	static int step=0;//递归深度
	//递归函数
	public static void sort(int begin ,int end) {
		if(end - begin <= 1) {//开始数据和结束数据是相邻数据时,不需要递归
			if(arr[begin] > arr[end]) {
				arr[begin] = arr[begin]+arr[end];//交换数据
				arr[end] =arr[begin] - arr[end];
				arr[begin] =arr[begin]-arr[end];
			}
		}else {
			int mid = (begin + end)/2;//
			s++;
			if(s>step) {//计算递归深度
				step=s;
			}
			sort(begin ,mid);//数据的左半边进行递归排序
			sort(mid+1 ,end);//数据的右半边进行递归排序
			s--;
			mergeSort(begin ,mid ,end);//对数组的两个区间进行排序
		}
	}
	//排序函数
	public static void mergeSort(int begin ,int mid ,int end) {
		int i = begin;
		int j = mid+1;
		int index = begin;
		while(i <= mid && j <= end) {
			if(arr[i] > arr[j])
				result[index++] = arr[j++];
			else
				result[index++] = arr[i++];
		}
		if(j > end)//说明排序数据左区间有数据还未复制
			for(;i < mid+1;i++)
				result[index++] = arr[i];//复制数据
		else//说明排序数据右区间有数据还未复制
			for(;j < end+1;j++)
				result[index++] = arr[j];
		for(i=begin ;i<end+1 ;i++)//把已经排序好的数据重新复制到arr数组
			arr[i] = result[i];//复制数据
	}
	public static void main(String[] args) {
		arr= new int[]{4,5,6,1,2,3,7,8,9,0};
		result=new int[arr.length];
		sort(0, arr.length-1);
		for(int i=0;i<result.length;i++)
			System.out.print(result[i] + " ");
		
		System.out.println();
		System.out.println("递归深度:"+step);
	}
}

如需要时间空间复杂度,请自行百度

参照文章:https://www.cnblogs.com/onepixel/articles/7674659.html

理解万岁!



猜你喜欢
数据结构与算法 2536 百科:快速(Quicksort)是对冒泡的一改进。快速由C.A.R.Hoare在1960年提出。它的基本思想是:通过一趟将要的数据分割成独立的两部分,其中一部分的所有数据都比另
java基础 499 现了区别于synchronized同步锁的一乐观锁。JDK5之Java语言是靠synchronized关键字保证同步的,这是一独占锁,也是是悲观锁。2.CASCAS机制当中使用了3个基本操
数据结构与算法 3855 (英语:Heapsort)是指利用堆这数据结构所设计的一。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
数据结构与算法 324 思想:把所有需要的数据分成两个集合,一个是待集合,一个是已的集合,每次从未集合顺或随机拿取一个数据,把它加入到已集合使其有,直到未集合中的数据被取走完,结束
数据结构与算法 2879 快速流程--来自百度百科首先设定一个分界值,通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分
数据结构与算法 353 思想:希尔是插入的增强版,其主要的思想还是插入的思想。描述:在插入的基础上,对待数组进行间隔为inc的分组,然后对每个分组进行直接插入,一次完成后,减小inc
数据结构与算法 379 思想:对冒泡的一改进,每次从没有的集合a中拿取一个最大或最小的元素,放入有的集合b中,直到a集合中的元素被取完描述:用变量i遍历整个数组,用变量j遍历i后面的数组,每次遍历i初始
数据结构与算法 386 思想该使用递归实现,思路为:每次递归将待数组在中间位置分成左右两组,分别对左右两个数组进行归并,递归的条件是数组长度必须大于等于3,所以当数组中只有两个数据的时候可以直接进行比较
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录