算法的时间复杂度
算法的时间复杂度和时间频度
时间频度
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]
时间复杂度中T(n) 表达式中的常数项、低次项、系数，可以忽略（随着n不断变大）
时间复杂度
算法的空间复杂度
排序算法（SortAlgorithm）
冒泡排序
思路：
案例：
如果我们发现在其中的一趟排序中没有交换，可以提前结束交换（优化）
代码：
public static void BubbleSort(int[] arr){
int temp = 0;
boolean flag = false;// 表示是不是进行过交换
for(int j=0;j<arr.length-1;j++){
for (int i = 0; i < arr.length-1-j; i++) {
// 如果前面的数比后面的数大就交换
if(arr[i]>arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
flag = true;
}
}
// System.out.println("第"+ (j+1) + "次排序后的结果：");
// System.out.println(Arrays.toString(arr));
if(flag == false){
System.out.println("没有发生交换了");
break;
}else{
flag = false;
}
}
}
选择排序
思路：
代码：
public static void selectSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i+1; j < arr.length; j++) {
if(min>arr[j]){
min = arr[j];
minIndex = j;
}
}
if(minIndex!=i){
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
插入排序
思路：
最差的时候： 每个数都要迁移index-1位置，n越大就越久
代码：
public static void insertSort(int[] arr){
int insertVal = 0;
int insertIndex = 0;
for (int i = 1; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i-1; // 待插入数前面的下标
while(insertIndex>=0 && insertVal < arr[insertIndex]){ // 保证这个insertVal 不越界 && 插入的位置还没找到
arr[insertIndex + 1] = arr[insertIndex];// 让值后移
insertIndex--;
}
if(insertIndex+1 != i){
arr[insertIndex + 1] = insertVal;// 插入的位置找到是insertIndex+1
// System.out.println(Arrays.toString(arr));
}
}
}
希尔排序(缩小增量排序)
思路：
示意图：
效果是尽量避免一个数移动多次的情况
代码：
public static void shellSort_Displacement(int[] arr) {
// gap ：步长
for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < arr.length; i++) {
// 从gap个元素，逐个对其所在的组进行直接插入排序
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
// 移动
arr[j] = arr[j - gap];
j -= gap;
}
// 退出while后找到了差插入的位置
arr[j] = temp;
}
}
// System.out.println(Arrays.toString(arr));
}
}
public static void shellSort_Swap(int[]arr){
// gap ：步长
for (int gap = arr.length/2;gap>0;gap = gap/2 ) {
int temp = 0;
for (int i = gap; i < arr.length; i++) {
for (int j = i-gap; j >=0 ; j-=gap) {
if(arr[j]>arr[j+gap]){
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
// System.out.println(Arrays.toString(arr));
}
}
快速排序
思路：
代码：
public static void quickSort(int []arr,int left,int right){
int l = left;
int r = right;
// 中轴
int pivot = arr[(left+right)/2];
int temp = 0;// 交换时候使用
// while循环的目的是为了让比pivot小的去左边，pivot大的去右边
while(l<r){
// 在pivot左边一直找，找到大于等于pivot的值，才退出
while(arr[l]<pivot){
l+=1;
}
// 在pivot右边一直找，找到小于等于pivot的值，才退出
while(arr[r]>pivot){
r-=1;
}
// 若果l>=r成立，说明pivot的左右两边的值，已经按照左边全部小于pivot，右边全部大于pivot排好了
if(l>=r){
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 交换完了，arr[l] == pivot的值相等。前移一步
if(arr[l] == pivot){
r-=1;
}
// 交换完了，arr[r] == pivot的值相等，r后移
if(arr[r] == pivot){
l+=1;
}
// （前后移） 退出循环，没必要进行操作了
}
// 如果l == r,必须l++,r--; 否则会出现栈溢出
if(l == r){
l+=1;
r-=1;
}
// 向左递归
if(left<r){
quickSort(arr,left,r);
}
// 向右递归
if(right>l){
quickSort(arr,l,right);
}
}
归并排序
思路：
代码：
// 分+合方法
public static void mergeSort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
// 先向左递归分解
mergeSort(arr,left,mid,temp);
// 然后向右分解
mergeSort(arr,mid+1,right,temp);
// 每分解一次就合并一次
merge(arr,left,mid,right,temp);
}
}
/**
*
* @param arr 要排序的数组
* @param left
* @param mid 中间索引
* @param right
* @param temp 中转数组
*/
public static void merge(int []arr,int left,int mid,int right,int []temp){
// System.out.println("xxx");
int i = left; // 初始化左边序列的初始索引
int j = mid+1;// 初始化右边序列的初始索引
int t = 0;
//(1)
// 先把左右两边的（有序）的数据按照规则填到数组里面
// 直到两边的有序序列有一边处理完为止
while(i<=mid && j<=right){
// 左边有序序列的当前元素小于等于右边元素
if(arr[i] <= arr[j]){
temp[t++] = arr[i++];
}else{
temp[t++] = arr[j++];
}
}
//(2)
// 把有剩余数据的一边数据依次完全填充到temp
while(i<=mid){
temp[t++] = arr[i++];
}
while(j<=right){
temp[t++] = arr[j++];
}
//(3)
// 将temp数组的元素拷贝到arr
// 并不是每次都拷贝所有数据到原来的数组 从下往治
t = 0;
int tempLeft = left;
// System.out.println("tempLeft = "+ tempLeft+",right = "+right);
while(tempLeft <= right){
arr[tempLeft++] = temp[t++];
}
}