Java排序-冒泡排序、插入排序和选择排序
文章目录
插入排序
1、特殊:从第二个元素开始,和第一个元素比较,如果满足排序的顺序,则交换顺序。
2、一般:把待比较和他之前的所有元素相比(从右往左),如果满足排序的顺序,这交换。
private static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++){ //从第二个元素开始
for (int j = i; j > 0; j--){ //这个元素和之前的元素比较
if (arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
2、冒泡排序
1、从第一个元素开始,和第二个元素相比,如果满足排序条件,则交换
2、把未排序的元素和后面的元素依次比较,如果满足排序条件,则交换
最初
private static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++){
for (int j = 0; j < arr.length - 1; j++){
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
因为每次循环后,i前面的元素已经排好序。所以可以进行优化。
优化后:
private static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length-1; i++){
for (int j = i+1; j < arr.length - 1; j++){
if (arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
3、选择排序
1、从第一个位置开始遍历待排序的元素,找到最小值和第一元素交换
2、从位置i开始往后遍历,找到i之后元素中的最小值,和第i个元素交换位置。
private static void selectSort(int[] arr){
int minLoc,temp;
for (int i = 0; i < arr.length-1; i++){
minLoc = i;
for (int j = i+1; j < arr.length; j++){
if (arr[j] < arr[minLoc]){
minLoc = j;
}
}
temp = arr[i];
arr[i] = arr[minLoc];;
arr[minLoc] = temp;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论