Java-排序算法

排序:按照指定的顺序排列出来.

升序:从小到大:

降序:从大到小.

--------------------------------------------

排序的分类:

选择排序(直接选择排序、堆排序)

交换排序(冒泡排序、快速排序)

插入排序(直接插入排序、二分法插入排序、Shell排序)

归并排序等。

排序有升序排列和降序排列之分,我们现在单讲升序排列:

我们主要讲解冒泡,选择,插入排序,当然在开发中因为性能问题,我们都不会自己写排序算法,不过排序在笔试题里却是常客。

若有下列int类型数组需要排序:

int[] arr = {2,9,6,7,4,1};

冒泡排序(Bubble Sort):

这是最简单的排序法,基本思路:

对未排序的各元素从头到尾依次比较相邻的两个元素大小关系,若大于则交换位置,经过第一轮比较排序后可得出最大值,然后使用同样的方法把剩下的元素

逐个比较即可。

可以看出若有N个元素,那么一共要进行N-1轮比较,第M轮要进行N-M次比较。(若6个元素,要进行6-1轮比较,第一轮比较6-1次,第三轮比较6-3次)。


选择排序(Selection Sort):

基本思路:选择某个索引位置的元素,然后和后面元素依次比较,若大于则交换位置,经过第一轮比较排序后可得出最小值,然后使用同样的方法把剩下的元

素逐个比较即可。

可以看出选择排序,第一轮会选出最小值,第二轮会选出第二小的值,直到最后。

第一轮从arr[0]和后面元素相比较,第二轮从arr[1]和后面的元素相比较,依次类推。N个数要进行N-1轮。选择排序每一轮只进行一次交换,相对于冒泡排

序效率高一些。

static void selectSort(int[] arr) {
	for (int times = 0; times < arr.length - 1; times++) {
		int minIndex = times;
		for (int i = times + 1; i < arr.length; i++) {
			if (arr[i] < arr[minIndex]) {
				minIndex = i;
			}
		}
		swap(arr, times, minIndex);
	}
}

版权声明:
作者:yfeer
链接:https://www.yfeer.com/545.html
来源:个人编程学习网
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>