专栏首页java初学java — 排序算法

java — 排序算法

1.冒泡排序

比较相邻元素,如果第一个比第二个大,就交换位置,每一次交换,当前

package BubbleSort;

public class Test 
{
	public static void main(String[] args)
	{
		int[] arr = {1,3,5,7,3,6,7,4,8,34,6};
		Test test = new Test();
		test.bubbleSort(arr);
		for(int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
	}

	public void bubbleSort(int[] num)
	{
		int temp = 0;
		for(int i = 0; i < num.length - 1; i++)
		{
			for(int j = i + 1; j < num.length; j++)
			{
				if(num[j-1] > num[j])
				{
					temp = num[j];
					num[j] = num[j - 1];
					num[j - 1] = temp;
				}
			}
		}
	}
			
}

2. 选择排序

从所有的数字中找到最小的数,放在第一个位置,然后从剩余的数字中找出次小的数,放在第二个位置,然后从剩下的数字中找出再次小的数,放在第三个位置......以此类推,直到所有的数据全部有序。

package SelectionSort;

public class Test 
{
	public static void main(String[] args)
	{
		int[] a = {4,2,1,6,3,6,0,-5,4,3};
		Test test = new Test();
		test.selectionSort(a);
		for(int i = 0; i < a.length; i++)
		{
			System.out.print(a[i] + " ");
		}
	}

	
	public void selectionSort(int[] source)
	{
		for(int i = 0; i < source.length; i++)
		{
			for(int j = i + 1; j < source.length; j++)
			{
				if(source[i] > source[j])
				{
					swap(source, i, j);
				}
			}
		}
	}
	
	private void swap(int[] source, int x, int y)
	{
		int temp = source[x];
		source[x] = source[y];
		source[y] = temp;
	}
}

  注意将选择排序和冒泡排序进行区分:冒泡排序是将相邻的数据进行对比,而选择排序是将下标为i和j的数据进行对比(每次选出当前数据集中最小的)。

3.插入排序

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

  ②取出下一个元素,在已经排序的元素序列中从后往前进行扫描;

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

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

  ⑤将该元素插入到新位置中;

  ⑥重复步骤②。

package InsertionSort;

public class Test 
{
	public static void main(String[] args)
	{
		int[] a = {4,5,3,2,6,5,6,43};
		Test test = new Test();
		test.selectSort(a);
		for(int i = 0; i < a.length; i++)
		{
			System.out.println(a[i]);
		}
	}
	
	public void selectSort(int[] source)
	{
		for(int i = 1; i < source.length; i++)
		{
			for(int j = i; j > 0 && source[j] < source[j - 1]; j--)
			{
				swap(source, j, j - 1);
			}
		}
	}
	
	public void swap(int[] source, int x, int y)
	{
		int temp = source[x];
		source[x] = source[y];
		source[y] = temp;
	}

}

空间复杂度:O(1)

时间复杂度:最优O(n),此时数组已经是升序排列,只需要完后n-1次比较即可;

      最坏O(n*n),此时数组已经是降序排列,此时需要进行n(n-1)/2次比较,赋值操作的比较次数是n(n-1)/2+(n-1)次。

平均时间复杂度:O(n*n)。

4.二分排序

二分法插入排序是在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上。

5.快速排序

package QuickSort;

public class Test 
{
	public static void main(String[] args)
	{
		int[] num = {3,4,5,32,3,5,2,78};
		Test test = new Test();
		test.quickSort(num, 0, num.length - 1);
		for(int i = 0; i < num.length; i++)
		{
			System.out.println(num[i]);
		}
	}

	
	public void quickSort(int[] a, int low, int high)
	{
		int start = low;
		int end = high;
		int key = a[low];
		
		while(end > start)
		{
			//从后往前比较
			//如果没有比关键字小,比较下一个,直到有比关键字小的交换位置,然后有从前往后比较
			while(end > start && a[end] >= key)
			{
				end--;
			}
			if(a[end] <= key)
			{
				int temp = a[end];
				a[end] = a[start];
				a[start] = temp;
			}
				//从前往后比较
				//如果没有比较关键字大的,比较下一个,直到有比关键字大的交换位置
			while(end > start && a[start] <= key)
			{
				start++;
			}
			if(a[start] >= key)
			{
				int temp = a[start];
				a[start] = a[end];
				a[end] = temp;
			}
			//此时第一次循环比较结束,关键字的位置已经确定了,左边的值都比关键字小,右边的值都比关键字大,但是两边的顺序可能不一样,进行
			//递归运算
		}
		if(start > low)
			quickSort(a, low, start - 1);//左边序列,第一个索引位置到关键字索引-1
		if(end < high)
			quickSort(a, end + 1, high);//右边序列,从关键字索引+1到最后一个
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • dubbo源码分析1——负载均衡

    Mister24
  • dubbo源码分析1——负载均衡

    Mister24
  • java — 设计模式

    Mister24
  • P3371 【模板】单源最短路径

    题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式: 第一行包含三个整数N、M、S,分别表示点的个数、有...

    attack
  • 挑战程序竞赛系列(31):4.5剪枝

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 算法复杂度分析

    为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

    前朝楚水
  • 程序员面试50题—栈的应用(7)

    #include<iostream> using namespace std; //void f1(const int& v1,const int& v2) ...

    互联网金融打杂
  • Vijos P1786 质因数分解【暴力】

    质因数分解 背景 NOIP2012普及组第一题 描述 已知正整数n是两个不同的质数的乘积试求出较大的那个质数。 格式 输入格式 输入只有一行包含一个正整数n。 ...

    Angel_Kitty
  • P1807 最长路_NOI导刊2010提高(07)

    题目描述 设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间...

    attack
  • 1265. [NOIP2012] 同余方程

    1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

    attack

扫码关注云+社区

领取腾讯云代金券