1、冒泡排序（两两比较相邻的元素，交换位置）
实现：
private static void BubbleSort(int[] arr,int n){
for(int i = 0;i
for(int j = 1;j
if(arr[j-1] > arr[j]){
//交换两个元素
int temp = arr[i];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
特点总结：
冒泡排序的算法时间平均复杂度为O(n²)。
空间复杂度为 O(1)。
冒泡排序为稳定排序。
2、选择排序
1、从待排序序列中，找到关键字最小的元素；起始假定第一个元素为最小
2、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
3、从余下的 N - 1 个元素中，找出关键字最小的元素，重复1，2步，直到排序结束。
实现：
public static void sort(int[] arr) {
int n = arr.length;for(int i = 0; i < n; i++) {
int minIndex = i;
//for循环 i 之后所有的数字 找到剩余数组中最小值得索引
for(int j = i + 1; j < n; j++) {
if(arr[j]< arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
/** * 角标的形式 交换元素 */
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
选择排序总结：
1、选择排序的算法时间平均复杂度为O(n²)。
2、选择排序空间复杂度为 O(1)。
3、选择排序为不稳定排序。
3、插入排序
插入排序的思想
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
6、重复步骤 2~5
实现：
public static void sort(int[] arr) {
int n = arr.length;for(int i = 0; i < n; i++) {
//内层循环比较 i 与前边所有元素值，如果 j 索引所指的值小于 j- 1 则交换两者的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
swap(arr,j-1,j);
}
}
}
或者这样实现：
public static void sort(int[] arr) {
int n = arr.length;for(int i = 0; i < n; i++) {
//拎出来当前未排序的这样牌
int e = arr[i];
//寻找其该放的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
arr[j]= arr[j-1];
}
//循环结束后 arr[j] >= arr[j-1] 那么 j 角标就是e 应该在的位置。
arr[j] = e;
}
}
插入排序总结：
1、插入排序的算法时间平均复杂度为O(n²)。
2、插入排序空间复杂度为 O(1)。
3、插入排序为稳定排序。
4、插入排序对于近乎有序的数组来说效率更高，插入排序可用来优化高级排序算法
4、归并排序
实现思想：
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针到达序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
转载自：https://juejin.im/post/5a96d6b15188255efc5f8bbd?utm_source=gold_browser_extension
网友评论