冒泡排序
什么是冒泡排序
- 先通过元素进行比较找出最大数，如果是升序就放在最后，降序就放在首位，
- 每次遍历都确定一个数的位置
算法思路
- 从后往前比较相邻的元素，如果后一个比前一个小，就互换位置
- 针对所有的元素重复以上的步骤。
算法模型
public void sort(int[] nums) {
for(int i=0;i< nums.length;i++){
boolean flag = true;
for(int j= nums.length-1;j>i;j--){
if(num[j]<nums[j-1]){
int temp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = temp;
flag = false;
}
}
if(flag){
break;
}
}
}
插入排序
什么是插入排序
对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法思路
- 将第一个元素看做一个有序序列，把其他元素当成是未排序序列
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置
算法模型
public void 插入Sort() {
int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
int j = 0;
for(int i=0;i<num.length;i++){
int temp = num[I];
// 将小于当前位置的数后移
for(j=i;j>0&&temp>num[j-1];j--){
num[j] = num[j-1];
}
num[j] = temp;
}
System.out.println(Arrays.toString(num));
}
选择排序
算法思路
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 重复第二步，直到所有元素均排序完毕。
算法模型
public void 选择Sort(){
int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
for(int i=0;i<num.length-1;i++){
int minIndex = i;
for(int j=i;j<num.length;j++){
if(num[j]<num[minIndex]){
minIndex = j;
}
}
if(i!=minIndex){
int temp = num[minIndex];
num[minIndex] = num[i];
num[i] = temp;
}
}
System.out.println(Arrays.toString(num));
}
快速排序
算法思路
- 选基准
- 分区
- 对分区迭代进行1，2步骤
算法模型
public void 快速Sort(){
int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
quickSort(num,0,num.length-1);
System.out.println(Arrays.toString(num));
}
private void quickSort(int[] num,int left,int right){
//递归结束条件左指针大于等于右指针
if(left<right) {
//分区
int partitionIndex = partition(num, left, right);
//递归左分区
quickSort(num, left, partitionIndex-1);
//递归右分区
quickSort(num, partitionIndex+1, right);
}
}
private int partition(int[] num,int left,int right){
int pivot = left;
int index = pivot+1;
for(int i = index;i<=right;i++){
if(num[i]<num[pivot]){
swap(num,i,index);
index++;
}
}
swap(num,pivot,index-1);
return index-1;
}
归并排序
算法思路
- 递归将数组拆成左右两个数组
- 递归返回时，将左右两个数组合并成有序数组
算法模版
public void 归并Sort(){
int[] num = new int[]{2,3,5,3,2,1,8,9,14,6,8,4};
num = mergeSort(num);
System.out.println(Arrays.toString(num));
}
private int[] mergeSort(int[] num){
if(num.length<2){
return num;
}
int[] left = Arrays.copyOfRange(num,0,num.length/2);
int[] right = Arrays.copyOfRange(num,num.length/2,num.length);
return merge(mergeSort(left),mergeSort(right));
}
private int[] merge(int[] left,int[] right){
int i = 0;
int j = 0;
int[] result = new int[left.length+right.length];
int cur;
while(i<left.length||j<right.length){
if(i==left.length){
cur = right[j++];
}else if(j==right.length){
cur = left[i++];
}else if(left[i]<=right[j]){
cur = left[i++];
}else{
cur = right[j++];
}
result[i+j-1] = cur;
}
return result;
}
