Java的时间复杂度和空间复杂度和常见排序

一丶时间复杂度

二丶空间复杂度

三丶Java常见排序

1. 冒泡排序（Bubble Sort）

2.插入排序（Insertion Sort）

3.希尔排序（Shell Sort）

4.选择排序（Selection Sort）

5.堆排序（Heap Sort）

6.归并排序（Merge Sort）

7.快速排序（Quick Sort）

8.计数排序（Counting Sort）、桶排序（Bucket Sort）和基数排序（Radix Sort）

简介：时间复杂度和空间复杂度是评估算法性能的两个重要指标，他们分别用于衡量算法执行时间长短和算法所存储空间大小；

一丶时间复杂度

时间复杂度：他描述了算法执行所需时间和数据规模之间的关系。具体来说，时间复杂度是算法中基本操作语句执行的次数，这次次数随着数据规模的增大而增大。时间复杂度通常用大O表示法（Big O notation）来表示，他忽略了常数因子和低阶项，只保留最高阶项，从而简洁明了的表示出算法的时间增长趋势；例如

O(1)：表示算法的执行时间是固定，与输入规模无关；
O(log n)：表示算法的执行时间与输入规模的对数成正比；
O(n)：表示线性时间复杂度，算法的执行时间与输入规模成线性比例增长；
O(n log n)：表示算法的执行时间与输入规模的线性对数比例增长；
O(n^2)：表示平方时间复杂度，算法的执行时间与输入规模的平方成比例增长。

通过分析算法的时间复杂度，可以评估算法的性能，优化算法的效率，从而提高程度的执行速度。

二丶空间复杂度

空间复杂度：它描述了算法在运行过程中临时占用存储空间的大小与数据规模之间的关系。空间复杂度也是用大O表示法来表示，他衡量的是算法运行过程中额外消耗的存储空间。例如

O(1)：表示算法的空间复杂度是固定的，与输入规模无关；
O(log n)：表示线性空间复杂度，算法所需内存与输入规模成线性比例增长
O(n^2)：表示平方空间复杂度，算法所需内存与输入规模的平方成比例增长。

通过分析算法的空间复杂度，可以避免内存的浪费，提高空间利用率，从而降低算法执行成本，提高程序性能；

三丶Java常见排序

1. 冒泡排序（Bubble Sort）

原理：通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复的进行直到没有再需要交换，也就是说该数列已经排序完成。

特点：简单，稳定，单效率低。时间复杂度O(n^2),空间复杂度O(1);

    //冒泡排序public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}

2.插入排序（Insertion Sort）

原理：通过构建有序序列，对于未排序数据，在已排序序序列中从后向前扫描，找到相应位置插入；

特点：稳定排序，适用于少量数据的排序，但是数据接近有序时效率较高。时间复杂度最好的情况下O(n),最坏的情况下O(n^2);空间复杂度O(1)；

    //直接插入排序public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {//取出第二个数据，默认已经排序int key = arr[i];//获取前以为数据的索引int j = i-1;/* 将 arr[0..i-1] 中大于 key 的元素移动到其当前位置的前 1 个位置*/while (j >=0 && arr[j] > key) {arr[j+1] = arr[j];j = j-1;}arr[j+1] = key;}}

3.希尔排序（Shell Sort）

原理：是插入排序的一种更高效的改进版本。希尔排序又称为缩小量排序，它将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序，在对全体记录进行直接插入排序；

特点：不稳定的排序，时间复杂度依赖于增量序列的选择，但平均性能优于直接插入排序；

时间复杂度：O(n^1.3)，空间复杂度O(1);

    //直接排序public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i += 1) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}

4.选择排序（Selection Sort）

原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；

特点：不稳定排序，时间复杂度：O(n^2)，空间复杂度：O(1)；

    //选择排序public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {int min_idx = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将找到的 Minimum 元素与第一个元素交换int temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}}

5.堆排序（Heap Sort）

原理：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）他的父节点；

特点：不稳定排序，时间复杂度：O(n log n)，空间复杂度：O(1)；

// 构建最大堆（辅助函数）  
void buildMaxHeap(int arr[]) {  int n = arr.length;  for (int i = n / 2 - 1; i >= 0; i--)  heapify(arr, n, i);  
}  // 调整给定的堆  
void heapify(int arr[], int n, int i) {  int largest = i; // 初始化最大为根  int l = 2 * i + 1; // 左 = 2*i + 1  int r = 2 * i + 2; // 右 = 2*i + 2  // 如果左子节点大于根  if (l < n && arr[l] > arr[largest])  largest = l;  // 如果右子节点是最大值  if (r < n && arr[r] > arr[largest])  largest = r;  // 如果最大值不是根  if (largest != i) {  int swap = arr[i];  arr[i] = arr[largest];  arr[largest] = swap;  // 递归地堆化受影响的子树  heapify(arr, n, largest);  }  
}  // 堆排序函数  
void heapSort(int arr[]) {  int n = arr.length;  buildMaxHeap(arr);  // 一个个从堆顶取出元素  for (int i = n - 1; i > 0; i--) {  // 移动当前根到末尾  int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  // 调用max heapify on the reduced heap  heapify(arr, i, 0);  }  
}

6.归并排序（Merge Sort）

原理：是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序；

特点：稳定排序，时间复杂度：O(n log n)，空间复杂度：O(n)；

public void mergeSort(int[] arr, int l, int r) {  if (l < r) {  // Same as (l+r)/2, but avoids overflow for  // large l and h  int m = l+(r-l)/2;  // Sort first and second halves  mergeSort(arr, l, m);  mergeSort(arr, m+1, r);  merge(arr, l, m, r);  }  
}  // 合并两个已排序的数组部分  
void merge(int arr[], int l, int m, int r) {  // Find sizes of two subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  /* Create temp arrays */  int L[] = new int[n1];  int R[] = new int[n2];  /*Copy data to temp arrays*/  for (int i=0; i<n1; ++i)  L[i] = arr[l + i];  for (int j=0; j<n2; ++j)  R[j] = arr[m + 1+ j];  /* Merge the temp arrays */  // Initial indexes of first and second subarrays  int i = 0, j = 0;  // Initial index of merged subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  } else {  arr[k] = R[j];  j++;  }  k++;  }  /* Copy remaining elements of L[] if any */  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  /* Copy remaining elements of R[] if any */  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  
}

7.快速排序（Quick Sort）

原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列；

特点：平均时间复杂度：O(n log n)，但是最坏的情况下时间复杂度会变成O(n^2)。空间复杂度取决于递归深度，平均为O(n log n)，但最坏情况下需要O(n)的额外空间；

public void quickSort(int[] arr, int low, int high) {  if (low < high) {  // pi is partitioning index, arr[p] is now  // at right place  int pi = partition(arr, low, high);  // Separately sort elements before  // partition and after partition  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}  // 该方法用于分区数组，返回分区索引  
int partition(int arr[], int low, int high) {  int pivot = arr[high];  int i = (low - 1); // index of smaller element  for (int j = low; j < high; j++) {  // If current element is smaller than or  // equal to pivot  if (arr[j] <= pivot) {  i++;  // swap arr[i] and arr[j]  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  // swap arr[i+1] and arr[high] (or pivot)  int temp = arr[i + 1];  arr[i + 1] = arr[high];  arr[high] = temp;  return i + 1;  
}