排序方法
内部排序: 数据全部加载进内存,
外部排序: 数据量过大, 无法全部加载进内存, 需要借助外存来进行排序
内部排序
插入排序: 直接插入排序, 希尔排序
选择排序: 简单选择排序, 堆排序
交换排序: 冒泡排序, 快速排序
归并排序:
基数排序:
算法的时间复杂度
基本介绍
时间频度: 一个算法花费的时间与算法中语句执行的次数成正比, 那个算法中语句执行次数越多, 它花费的时间也就越多, 一个语句执行的次数称之为语句频度或者时间频度, 记为T(n).
忽略常数项(也就是看循环)
忽略低次项
忽略系数
也就是说T(n)不同, 但是时间复杂度可能相同.
T(n) -> f(n) -> O(f(n))
常见的时间复杂度大小梯队
O(1)
冒泡排序
import java.util.Arrays;
public class Maopao {
public static void main(String[] args) {
int[] arr = {3,4,5,6,8,7};
int temp = 0;
for (int i = 1; i <= arr.length-1; i++){ //第一层循环表示第几趟,
for (int j = 0; j < arr.length-i; j++){ //length-i, 这里的i 表示到了倒数的第i个元素, 就不需要再和后面的数比较了, 因为要么是数组的最后, 要么是上一趟冒出来的最大值.
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第"+i+"趟排序后为:");
System.out.println(Arrays.toString(arr));
}
//优化写法
int temp1 = 0;
boolean flag = false; //判断该趟是否有发生换位, 默认没有
for (int i = 1; i <= arr.length-1; i++){ //第一层循环表示第几趟,
for (int j = 0; j < arr.length-i; j++){ //length-i, 这里的i 表示到了倒数的第i个元素, 就不需要再和后面的数比较了, 因为要么是数组的最后, 要么是上一趟冒出来的最大值.
if (arr[j] > arr[j+1]){
temp1 = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp1;
flag = true;
}
}
System.out.println("第"+i+"趟排序后为:");
System.out.println(Arrays.toString(arr));
if (flag){
flag = false;
}else{
break;
}
}
}
}
选择排序
思想: 第一次从arr[0]~到arr[n-1]中选取最小值, 与arr[0]交换, 第二次从arr[1]~arr[n-1]中选取最小值, 与arr[1]交换,以此类推
import java.util.Arrays;
public class Xuanze {
public static void main(String[] args) {
int[] arr = {1,2,4,3,5,6};
for (int i = 0; i < arr.length-1; i++){ //永远都是拿前面的一个做预设的min, 所以要length-1. 因为只用到倒数第二个的位置
int minIndex = i;
int min = arr[i];
for (int j = i+1; j < arr.length; j++){ //永远都是拿预设的min和它之后的每一个数比较, 冲突则改min
if (min > arr[j]){
min = arr[j];
minIndex = j;
}
}
if (minIndex != i){ //如果min不是预设的, 位置交换
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println("第"+(i+1)+"趟排序后:");
System.out.println(Arrays.toString(arr));
}
//没法像冒泡一样做优化. 因为选择排序一定要执行到最后一趟才能完全确定是不是排序完成.
//不像冒泡, 只要有一次没有发生位置的交换就是排序好了.
}
}
插入排序
基本思路
把n个元素看成一个有序表和一个无序表, 开始时, 有序表中只有一个元素, 而无序表中有n-1个元素, 每次从无序表中拿出第一个元素, 把他的排序码和依次与有序表的排序码进行比较, 将他插入到有序表的适当位置.
import java.util.Arrays;
public class Charu {
public static void main(String[] args) {
int[] arr = {2,1,5,3,0};
for (int i = 1; i< arr.length; i++){ //从无序表的第一个找到最后一个
int wuxu1 = arr[i]; //每一次都先取出无序表的第一个数据
int youxuIndex = i-1; //每一次都从有序表的最后一个数据开始判断
while(youxuIndex >= 0 && wuxu1 < arr[youxuIndex]){
arr[youxuIndex+1] = arr[youxuIndex];
youxuIndex--;
}
arr[youxuIndex+1] = wuxu1;
System.out.println("第"+i+"趟排序后为:");
System.out.println(Arrays.toString(arr));
}
}
}
简单的插入排序有缺陷, 当后面的数越小, while循环的次数就越多
希尔排序, 也是一种插入排序, 但是效率更高, 也叫缩小增量排序
希尔排序: 交换法+移动法
这里我直接就只有移位法, 移位法来的好理解的多, 因为本来就是直接插入法的一种优化, 如果不知道直接插入法是怎么一回事, 确实理解起来会很困难. 但是如果直到了直接插入法的缺点在哪里之后, 就很容易理解希尔排序为什么要这么做.
public class Shell {
public static void main(String[] args) {
int[] arr = {9,8,7,6,5,4,3,2,1,0};
int count = 0;
for (int gap = arr.length/2; gap > 0; gap /= 2){
//其实这里就是直接插入排序
for (int i = gap; i < arr.length; i++){ //确保每一次都是拿到的该组的无序表的第一个元素, 或者更准确的说是, 先拿到每一组的无序表的第一个数
int j = i;
int temp = arr[i];
if (arr[i] < arr[i-gap]){
while(j-gap >=0 && temp < arr[j-gap]){
//移动
arr[j] = arr[j-gap];
j -= gap;
}
//每一次出这个while就说明temp已经找到了位置. 准确的说是在temp对应的组中找到了正确的位置
arr[j] = temp;
}
}
System.out.println("第"+(++count)+"趟之后的排序是"+ Arrays.toString(arr));
}
}
}
快速排序
思路
快速排序是冒泡排序的一种优化, 本质上也是交换排序
也是元素之间相互比较 , 然后交换位置
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
public class Kuaisu {
public static void main(String[] args) {
int[] arr = {5,6,89,45,1,0,32,54,88,412,986,4,2,6};
kuaisupaixu(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
static public void kuaisupaixu(int[] arr, int left, int right){
int l = left;
int r = right; //冒泡是以i和i+1来进行判断并交换, 但是快排使用的是l和r
int jishu = arr[(right+left)/2]; //基数
int temp = 0; //交换容器
while(l < r){ //如果没有交汇或者相遇, l和r继续前进
while(arr[l] < jishu){
l += 1;
}
while(arr[r] > jishu){
r -= 1;
}
if (l >= r){ //l和r一旦相遇或者交汇, 就意味着一轮的结束,
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == jishu){
r -= 1;
}
if (arr[r] == jishu){
l += 1;
}
}
if (l == r){
l += 1;
r -= 1;
}
if (left < r){
kuaisupaixu(arr, left, r);
}
if (right > l){
kuaisupaixu(arr, l, right);
}
}
}
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
由归并排序的这种分治思想可以知道
归并排序的归并次数永远都是arr.lenght-1次. 也即是数据的个数减一
所以归并排序是一种效率很好的排序.
public class Guibing {
public static void main(String[] args) {
int[] arr = {8,5,7,6,2,4,3,1,0};
int[] tempArr = new int[arr.length];
fenAndzhi(arr, 0, arr.length-1, tempArr);
System.out.println("归并排序之后为:"+ Arrays.toString(arr));
}
//分+治的算法
//用于递归
static public void fenAndzhi(int[] arr , int left, int right , int[] tempArr){
if (left < right){
int mid = (left+right)/2;
//向左递归
fenAndzhi(arr, left, mid, tempArr);
//向右递归
fenAndzhi(arr, mid+1, right, tempArr);
//治
zhi(arr, left, right, mid, tempArr);
}
}
//治的算法
static public void zhi(int[] arr , int left , int right , int mid, int[] tempArr){
int i = left; //左子集的开始索引
int j = mid +1; //右子集的开始索引
int t = 0; //占存数组的开始索引
while (i <= mid && j <= right){
if (arr [i] <= arr[j]){
tempArr[t] = arr[i];
i++;
t++;
}else{
tempArr[t] = arr[j];
j++;
t++;
}
}
//有一边会剩数
while (i <= mid){
tempArr[t] = arr[i];
t++;
i++;
}
while (j <= right){
tempArr[t] = arr[j];
t++;
j++;
}
//分治思想: 其实每一次都是前面的两个先治, 顺序向后
//所以temp的数据可以直接替换arr的数据
//例如这里治的顺序就是(0~1)(2~3)(0~3)(4~5)(6~7)(4~7)(0~7)
t = 0;
int l = left; //确定放在arr的哪里
while (l <= right){
arr[l] = tempArr[t];
l++;
t++;
}
}
}
