选择排序
遍历查找数组中最小数
将它与原本处于最小值位置的数字交换
实现
//选择排序
public class SelectionSort {
private SelectionSort(){
}
public static void sort(int[] arr ){
int n = arr.length;//数组长度
for (int i = 0;i<n;i++){
int min = i;//存储每次比较那个最小的数下标（一开始只有一个数默认它为最小）
//往后循环 拿到它所得到最小的那个数的下标
for (int j = i+1;j<n;j++){
if (arr[min] > arr[j]){
min = j;//储存最小的那个数的下标
}
}
swap(arr, min, i);//然后与它从小到大排序的那位数交换
}
}
private static void swap(int arr[],int i,int j){
int temp = arr[i];//每次遍历最小的那个数
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10,9,8,7,6,5,4,3,2,1};
SelectionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
}
}
效果:
插入排序
分为左右两个排序数组
左边默认为排好序
右边第一个元素与左边数组最后一位比较
若小于则交换 继续与最后一位的前一位进行对比 以此类推
实现:
//插入排序实现
public class InsertSort {
private InsertSort(){
}
public static void insert(int[] arr){
int n = arr.length;
//这里i=1因为不用考虑第一个元素
// 默认就是有序的
//分为左右有序列和无序列，一开始存储的元素
// 与有序列进行比较
for (int i = 1;i<n;i++){
for (int j = i;j>0;j--){
//如果j比它前一个元素还小
if(arr[j] < arr[j-1]){
//则互换位置
swap(arr, j, j-1);
}
}
}
}
private static void swap(int arr[],int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10,9,8,5,6,7,4,3,2,1};
InsertSort.insert(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
}
}
选择排序与插入排序之间的区别:
选择排序是选取一个最小数，然后不断与后面的元素进行比较，存储最后比较到的最小的数并插入（temp值一直在变化）
插入排序是分成有序列与无序列，新加入有序列的元素与已在有序列中的元素互相比较（相当与往前一个个地比较）
冒泡排序
冒泡排序就是不断地进行两两互换
public class BubbleSort {
private BubbleSort(){
}
public static void bubble(int arr[]){
int n = arr.length;
boolean swapped = false;//判断它是否互换过
do {
swapped = false;
for (int i = 1;i<n;i++){
if(arr[i] < arr[i-1]){
swap(arr, i-1, i);
swapped = true;
}
}
// 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
// 所以下一次排序, 最后的元素可以不再考虑
n --;
}while (swapped);
}
private static void swap(int arr[],int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10,9,8,7,6,5,4,3,2,1};
BubbleSort.bubble(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(" ");
}
System.out.println();
}
}
