当前位置 博文首页 > 邱天的henry的博客：第七章 数据结构与算法（八大排序算法--堆排
7.1冒泡算法
7.1.1基本介绍
（1）冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
（2）优化：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行交换。从而减少不必要的比较。（这里说的优化，可以在冒泡排序写好后，在进行）
7.1.2演示冒泡过程的例子（图解）
小结以上图解：
（1）一共进行（数组的大小-1）次 大的循环
（2）每一趟排序的次数在逐渐的减少
（3）如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。这个就是优化。
7.1.3冒泡排序应用实例
@将五个无序的数：3,9，-1,10，-2使用冒泡排序法将其排成一个从小到大的有序数列。
public class Demo1 {
public static void main(String[] args) {
//为了便于理解，冒泡排序的演变过程如下
/*int[] arr={3,9,-1,10,-2};
//起始的数组为
System.out.println("初始的数组为：");
System.out.println(Arrays.toString(arr));*/
//测试冒泡排序的时间O(n^2)
//定义一个随机数组
int[] arr=new int[80000];
for (int i=0;i<80000;i++){
arr[i]=(int)(Math.random()*800000); //math.random的范围是[0,1)
}
//输出起始时间
long time = System.currentTimeMillis();
System.out.println(time);
//调用封装好的冒泡方法
bubbleSort(arr);
//排序后时间
long time2 = System.currentTimeMillis();
System.out.println(time2);
//排序后的数组为
/*System.out.println("排序后的数组为：");
System.out.println(Arrays.toString(arr));*/
/*//第二趟排序
for (int j=0;j<arr.length-1-1;j++){
if (arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
//第三趟排序
for (int j=0;j<arr.length-1-2;j++){
if (arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
//第四趟排序
for (int j=0;j<arr.length-1-3;j++){
if (arr[j]>arr[j+1]){
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}*/
}
//将冒泡排序封装为方法
public static void bubbleSort(int[] arr){
int temp=0; //临时变量
boolean flag=false; //定义标识符，判断每一趟是否交换过
//冒泡排序时间复杂度为O(n^2)
for (int i=0;i<arr.length-1;i++){
for (int j=0;j<arr.length-1-i;j++){
if (arr[j]>arr[j+1]){
flag=true; //如果交换就将flag置位true
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
//System.out.println("第"+(i+1)+"趟排序后的数组为：");
//System.out.println(Arrays.toString(arr));
if (!flag){
break; //结束循环（因为此趟没有交换数组位置，说明数组已经有序）
}else {
flag=false; //如果此趟交换过位置，需要将flag重置，以便于下一轮的循环
}
}
}
}
7.2选择排序
7.2.1基本介绍
选择排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出来某一元素，再一次规定交换位置后达到排序的目的。
7.2.2选择排序思想
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]-arr[n-1]中选取最小值，与arr[2]交换，…, 第i次从arr[i-1]-arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]-arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
7.2.3选择排序的思路图
7.2.4选择排序实例
@将数组101,34,119,1进行排序
public class SelectSort {
public static void main(String[] args) {
//int[] arr={101,34,119,1};
//System.out.println("起始数组");
//System.out.println(Arrays.toString(arr));
//定义一个随机数组（测试时间：时间比冒泡排序快）
int[] arr=new int[80000];
for (int i=0;i<80000;i++){
arr[i]=(int)(Math.random()*800000); //math.random的范围是[0,1)
}
//起始时间
System.out.println(System.currentTimeMillis());
selectSort(arr);
//排序后时间
System.out.println(System.currentTimeMillis());
//System.out.println("排序后数组");
//System.out.println(Arrays.toString(arr));
}
//选择排序算法
public static void selectSort(int[] arr){
//算法 先简单--》做复杂，就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决
//冒泡时间复杂度为O(n^2)
//第一轮
for (int i=0;i<arr.length-1;i++){
int minIndex=i; //假设起始数小标为最小下标
int min=arr[minIndex]; //假设起始数为最小值
for (int j=i+1;j<arr.length;j++){
if (arr[j]<min){ //判断循环的数是否比假设的起始值小，如果小则交换
minIndex=j; //交换最小值下标
min=arr[j]; //交换最小值
}
}
if (minIndex !=i){ //如果最小值不为当前假设值才可进入if语句
arr[minIndex]=arr[i];
arr[i]=min;
}
}
/*//第二轮
minIndex=1; //假设起始数小标为最小下标
min=arr[1]; //假设起始数为最小值
for (int j=1+1;j<arr.length;j++){
if (arr[j]<min){ //判断循环的数是否比假设的起始值小，如果小则交换
minIndex=j; //交换最小值下标
min=arr[j]; //交换最小值
}
}
if (minIndex !=1){ //如果最小值不为当前假设值才可进入if语句
arr[minIndex]=arr[1];
arr[1]=min;
}
//第三轮
minIndex=2; //假设起始数小标为最小下标
min=arr[2]; //假设起始数为最小值
for (int j=2+1;j<arr.length;j++){
if (arr[j]<min){ //判断循环的数是否比假设的起始值小，如果小则交换
minIndex=j; //交换最小值下标
min=arr[j]; //交换最小值
}
}
if (minIndex !=2){ //如果最小值不为当前假设值才可进入if语句
arr[minIndex]=arr[2];
arr[2]=min;
}*/
}
}
7.3插入排序
7.3.1插入排序法介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式寻找该元素的适当位置，以达到排序的母的。
7.3.2插入排序法思想
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
7.3.3插入排序思路图
7.3.4插入排序法应用实例：
@有一群小牛，考试成绩为101,34,119,1；请从小到大排序
public class InsertSort {
public static void main(String[] args) {
//int[] arr={101,34,119,1};
int[] arr=new int[80000];
for (int i=0;i<80000;i++){
arr[i]=(int)(Math.random()*800000); //math.random的范围是[0,1)
}
//起始时间
System.out.println(System.currentTimeMillis());
insertSort(arr);
//排序后时间
System.out.println(System.currentTimeMillis());
}
//插入排序
public static void insertSort(int[] arr){
int indexVal=0; //待排序的数
int beforeIndex=0;
//分步演示，便于理解
for (int i=1;i<arr.length;i++){
//第一轮（101,34,119,1） ==》（34,101,119,1）
indexVal=arr[i]; //待排序的数
beforeIndex=i-1; //待排序前面一个数的索引（从次数开始进行往前遍历）
//1.首先保证beforeIndex不越界
//2.保证待插入的值小于与之比较的值后方可进入循环
//3.满足条件就将待排序前一个数往后移，并将before--继续与前面的数比较
while (beforeIndex>=0 && indexVal<arr[beforeIndex]){
arr[beforeIndex+1]=arr[beforeIndex];
beforeIndex--;
}
//循环结束后，将待排序数插入(在循环的最后将beforeIndex--作为循环判断条件，所以要把待排序数放在后一位)
arr[beforeIndex+1]=indexVal;
// System.out.println("第"+i+"次排序后");
//System.out.println(Arrays.toString(arr));
}
/*//第二轮
indexVal=arr[2]; //待排序的数
beforeIndex=2-1; //待排序前面一个数的索引（从次数开始进行往前遍历）
while (beforeIndex>=0 && indexVal<arr[beforeIndex]){
arr[beforeIndex+1]=arr[beforeIndex];
beforeIndex--;
}
//循环结束后，将待排序数插入(在循环的最后将beforeIndex--作为循环判断条件，所以要把待排序数放在后一位)
arr[beforeIndex+1]=indexVal;
System.out.println("第二次排序后");
System.out.println(Arrays.toString(arr));
//第三轮
indexVal=arr[3]; //待排序的数
beforeIndex=3-1; //待排序前面一个数的索引（从次数开始进行往前遍历）
while (beforeIndex>=0 && indexVal<arr[beforeIndex]){
arr[beforeIndex+1]=arr[beforeIndex];
beforeIndex--;
}
//循环结束后，将待排序数插入(在循环的最后将beforeIndex--作为循环判断条件，所以要把待排序数放在后一位)
arr[beforeIndex+1]=indexVal;
System.out.println("第三次排序后");
System.out.println(Arrays.toString(arr));*/
