一、概述:
本文给出常见的几种排序算法的原理以及 Java 实现,包括常见的简单排序和排序算法,以及其他常用的算法知识。
- 简单排序:冒泡排序、选择排序、插入排序
- 排序:快速排序、归并排序、希尔排序
- 相关算法知识:划分、递归、二分查找
二、冒泡排序:
(1)原理:
- 1、从个数据开始,与第二个数据相比较,如果第二个数据小于个数据,则交换两个数据的位置。
- 2、指针由个数据移向第二个数据,第二个数据与第三个数据相比较,如果第三个数据小于第二个数据,则交换两个数据的位置。
- 3、依此类推,完成轮排序。轮排序结束后,更大的元素被移到了最右面。
- 4、依照上面的过程进行第二轮排序,将第二大的排在倒数第二的位置。
- 5、重复上述过程,没排完一轮,比较次数就减少一次。
(2)例子:
待排序数据:7, 6, 9, 8, 5,1
轮排序过程:
指针先指向7,7和6比较,6<7,交换6和7的位置,结果为:6,7,9,8,5,1
指针指向第二个元素7,7和9比较,9>7,不用交换位置,结果仍为:6,7,9,8,5,1
指针指向第三个元素9,比较9和8,8<9,交换8和9的位置,结果为:6,7,8,9,5,1
指针指向第四个元素9,比较9和5,5<9,交换5和9,结果为:6,7,8,5,9,1
指针指向第五个元素9,比较9和1,1<9,交换1和9的位置,结果为6,7,8,5,1,9
轮排序结束后,更大的数字9被移到了最右边。
进行第二轮排序,过程同上,只是由于更大的9已经放在最右边了,因此不用在比较9了,少了一次比较,第二轮结束的结果为:6,7,5,1,8,9
第三轮结果:6,5,1,7,8,9
第四轮比较结果:5,1,6,7,8,9
第五轮比较结果:1,5,6,7,8,9
最终排序结果为:1,5,6,7,8,9,由上可知N个数据排序,需要进行N-1轮排序;第i轮排序需要的比较次数为N-i次。
(3)编码思路:
需要两层循环,层循环i表示排序的轮数,第二层循环j表示比较的次数。
(4)代码实现:
实例
package com.test.insertsort;
@author
public class ChooseSort {
private int[] array;
private int length;
public ChooseSort(int[] array){
this.array = array;
this.length = array.length;
}
public void display(){
for(int i: array){
System.out.print(i+" ");
}
System.out.println();
}
public void chooseSort(){
for(int i=0; i<length-1; i++){
int minIndex = i;
for(int j=minIndex+1;j<length;j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
public static void main(String[] args){
int[] array={100,45,36,21,17,13,7};
ChooseSort cs = new ChooseSort(array);
System.out.println("排序前的数据为:");
cs.display();
cs.chooseSort();
System.out.println("排序后的数据为:");
cs.display();
}
}
我们凭借多年的网站建设经验,坚持以“
帮助中小企业实现网络营销化”为宗旨,累计为1000多家客户提供品质建站服务,得到了客户的一致好评。如果您有
网站建设、
网站改版、
百度优化、名注册、主机空间、
手机网站建设、
公众号开发、
小程序制作、网站备案等方面的需求...
请立即点击咨询我们或拨打咨询热线:
13820372851,我们会详细为你一一解答你心中的疑难。
项目经理在线