排序算法 :把乱序的数组按照一定的顺序排列.
排序算法有很多,这里练习的是选择排序法 和冒泡排序法 .
int[] a= {1,5,9,3,6,2};
以上面这个数组为例,数组长度为6,元素分别为a[0]-a[5]
选择排序法
选择排序法 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
选择排序的基本思想:
第1趟,在待排序记录a[0]-a[5]中选出最小的,将它与a[0]交换;
选择最小方法就是a[0]依次与a1,a2…a5比较,若a0>ai则交换这两个元素的值(地址)
第2趟,在待排序记录a[1]-a[5]中选出最小的,将它与a[1]交换;
以此类推,第i趟在待排序记录a[i]-a[n]中选出最小的,将它与a[i]交换,使有序序列不断增长直到全部排序完毕。
此算法中每比较一次都会交换一次,可以改良一下,每次比较只用变量记录下较小的角标,全部比较完成后,再与a[0]交换,这样可以提高效率.
冒泡排序法
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
冒泡排序法的基本思想:
第1趟,a0和a1比较并排序(大数靠后),然后a1和a2比较,a2和a3比较…直到最后.这一轮的结果是数组最大值移动到a5
第二趟,a0和a1比较,a1和a2…直到a4,这一轮的结果是a4是次大值.
以此类推
冒泡排序和选择排序的区别:
选择排序是每次比较的第一个不变,依次和后面的元素比较;
冒泡排序是每次比较的都是相邻的两个元素;
从比较的结果看(从小到大排序),
选择排序是每一轮都是选择最小的元素靠左排列
冒泡排序是每一轮选择最大的元素靠右排列
改良后的选择排序每次比较只记录下最值的位置,每轮只交换一次,
冒泡排序冒泡排序每轮只要相邻两个数不满足条件就要交换,
这样看选择排序要优于冒泡排序.
package PracticeFunction;
public class PrintChar {
public static void main ( String[ ] args) {
int [ ] arr = { 1 , 5 , 9 , 3 , 6 , 2 } ;
printArr ( arr) ;
bubbleSort ( arr) ;
printArr ( arr) ;
}
public static void selectSort ( int [ ] arr) {
for ( int i= 0 ; i< arr. length- 1 ; i++ ) {
for ( int j = i; j< arr. length; j++ ) {
if ( arr[ i] > arr[ j] ) {
exchange ( arr, i, j) ;
}
}
}
}
public static void bubbleSort ( int [ ] arr) {
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 ] ) {
exchange ( arr, j, j+ 1 ) ;
}
}
}
}
public static void exchange ( int [ ] arr, int a, int b) {
int temp = arr[ a] ;
arr[ a] = arr[ b] ;
arr[ b] = temp;
}
public static void printArr ( int [ ] arr) {
for ( int i= 0 ; i< arr. length; i++ ) {
if ( i== arr. length- 1 ) {
System. out. println ( arr[ i] ) ;
} else {
System. out. print ( arr[ i] + "," ) ;
}
}
}
}
改良版的选择排序:
public static void selectSort ( int [ ] arr) {
for ( int i= 0 ; i< arr. length- 1 ; i++ ) {
int min = i;
for ( int j = i; j< arr. length; j++ ) {
if ( arr[ i] > arr[ j] ) {
min = j;
}
else {
min = i;
}
}
exchange ( arr, i, min) ;
}
}
如果内容有错误,恳请大佬们指出,感谢!