|
1. 选择排序:
例如有下列数组 arr {20,25,30,15,10}.
第一次排序,让数组的第一位数与其后面的每一位数进行比较,将所比的最小的数字放到第一位.
(1)20与25相比较,20比25小,所以数组不变.
(2)20与30相比较,20比30小,所以数组不变.
(3)20与15相比较,20比15大,所以20与15位置交换.
(4)15与10相比较,15比10大,所以15与10位置交换.
这一步骤的程序可以写为
int[] arr = {20,25,30,15,10};
min = arr[0];
for(int i = 1;i<arr.lenght;i++){
iIf(min >arr){
inttemp = min;
min =arr;
arr= temp;
}
}
arr[0] = min;
经过第一个步骤的比较后,第一位变为了数组中最小的数,所以第二步从数组的第二位开始.
(1)25与30相比较,20比25小,所以数组不变.
(2)25与20相比较,25比20大,所以25与20位置交换.
(3)20与15相比较,20比15大,所以20与15位置交换.
这一步骤的程序可以写为
int[] arr = {10,25,30,20,15};
min = arr[1];
for(int i = 2;i<arr.lenght;i++){
iIf(min >arr){
inttemp = min;
min =arr;
arr= temp;
}
}
arr[1] = min;
经过第二个步骤的比较后,第二位的数变成了数组中第二小的数,第三步从数组的第三位开始.
(1)30与25相比较,30比25大,所以30与25位置交换.
(2)25与20相比较,25比20大,所以25与20位置交换.
这一步骤的程序可以写为
int[] arr = {10,15,30,25,20};
min = arr[2];
for(int i = 3;i<arr.lenght;i++){
iIf(min >arr){
inttemp = min;
min =arr;
arr= temp;
}
}
arr[2] = min;
接下来是最后一步,把第四位数字和第五位数字比较.
(1)30与25相比较,30比25大,所以30与25位置交换.
int[] arr = {10,15,20,30,25};
min = arr[3];
for(int i = 4;i<arr.lenght;i++){
iIf(min >arr){
inttemp = min;
min =arr;
arr= temp;
}
}
arr[3] = min;
通过上述步骤,我们发现这个四个程序唯一在变的是min的初始值,数组和for中i的值.
所以我们可以通过在外面加一个for循环来构成一个循环的嵌套来完成程序.
int[] arr = {20,25,30,15,10};
for(int i = 0; i < arr.length-1;i++){
int min = arr;
for(int j = i+1;j<arr.length;j++){
if(min> arr[j]){
int temp = min;
min = arr[j];
arr[j] = temp;
}
}
arr = min;
}
2. 冒泡排序:
数组与选择排序的数组相同 arr {20,25,30,15,10}.
第一次排序,让数组的每一位数与其后一位数进行比较,将所比的较小的数字放到前,较大的数字放到后.
(1)20与25相比较,20比25小,所以数组不变.
(2)25与30相比较,25比30小,所以数组不变.
(3)30与15相比较,30比15大,所以30与15位置交换.
(4)30与10相比较,30比10大,所以30与10位置交换.
for(inti = 0 ; i < 4 ; i++ ){
if(arr> arr[i+1]){
inttemp = arr[i+1];
arr[i+1]= arr;
arr= temp;
}
}
第二次排序,让数组的前三位数与其后一位数进行比较,将所比的较小的数字放到前,较大的数字放到后.与第一次排序相比只需要进行三次排序.
(1)20与25相比较,20比25小,所以数组不变.
(2)25与15相比较,25比15大,所以25与15位置交换.
(3)25与10相比较,25比10大,所以25与10位置交换.
for(int i = 0 ;i < 3 ; i++ ){
if(arr> arr[i+1]){
inttemp = arr[i+1];
arr[i+1]= arr;
arr= temp;
}
}
第三次排序,让数组的前两位数与其后一位数进行比较,将所比的较小的数字放到前,较大的数字放到后.与第一次排序相比只需要进行两次排序.
(1)20与15相比较,20比15大,所以20与15位置交换.
(2)20与10相比较,20比10大,所以20与10位置交换.
for(int i = 0 ;i < 2 ; i++ ){
if(arr> arr[i+1]){
inttemp = arr[i+1];
arr[i+1]= arr;
arr= temp;
}
}
第四次排序,让数组的第一位数与其后一位数进行比较,将所比的较小的数字放到前,较大的数字放到后.与第一次排序相比只需要进行一次排序.
(1)20与15相比较,20比15大,所以20与15位置交换.
(2)20与10相比较,20比10大,所以20与10位置交换.
for(int i = 0 ;i < 2 ; i++ ){
if(arr> arr[i+1]){
inttemp = arr[i+1];
arr[i+1]= arr;
arr= temp;
}
}
通过上述步骤,我们发现这个四个程序唯一在变的是数组和for中i最大值.
所以我们可以通过在外面加一个for循环来构成一个循环的嵌套来完成程序.
int[]arr = {20,25,30,15,10};
for(intj = arr.length – 1 ; j >= 0 ; j-- ){
for(inti = 0 ; i < j ; i++){
if(arr> arr[i+1]){
inttemp = arr[i+1];
arr[i+1]= arr;
arr= temp;
}
}
}
以上就是数组的选择排序和冒泡排序.
他们的区别是:
选择排序是每一排序一轮确定一个位置的数.
冒泡排序则是每一轮确定一个数的位置.
冒泡排序对数组排序,其空间上的前后顺序并不会因为排序而发生改变,但是由于其相比较的两个数不停的变化,会使其复杂程度大大提升.
选择排序一轮比较只需要变换一个位置的数字,可以使其排序是的复杂性大大降低,但是如上所述,其破坏了数组中相同数的前后顺序.
|
