以前一直想总结一遍没总结,这次在甲级题中竟然考出来两种排序算法的比较,于是干脆把所有的排序算法总结一遍,供以后复习使用.
复杂度O(n^2)的有冒泡,插入,选择
复杂度O(nlogn)的有快速,归并,堆排序
1.冒泡排序(n^2)
思想:排n次,每次把没排好的最大的挑出来,然后排到后面去,最大的排最后面,次大的排倒数第二个..
加一个flag优化一下
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> a = {9,8,7,6,5,4,3,2,1};
int flag = 1;
int num=0;
for(int i=0;i<a.size()&&flag==1;i++){
flag = 0;
for(int j=0;j<a.size()-i-1;j++){
num++;
if(a[j+1]<a[j]){
swap(a[j],a[j+1]);
flag = 1;
}
}
}
for(int i=0;i<a.size();i++){
cout<<a[i]<<" ";
}
cout<<endl<<num;
}
2.快速排序(nlogn)
每次挑一个标志值,在一遍排序后,前面的值都比标志值小,后面的都比标志值大.
时间复杂度nlogn
public class QuickSort {
public static void main(String[] args) {
int[] a = {5, 8, 4, 2, 6, 1, -2, 8};
quicksort(a, 0, a.length - 1);
for (int i : a) {
System.out.print(i + " ");
}
}
private static void quicksort(int[] a, int low, int high) {
if (low < high) {
int index = getIndex(a, low, high);
quicksort(a, low, index - 1);
quicksort(a, index + 1, high);
}
}
private static int getIndex(int[] a, int low, int high) {
int tmp = a[low];
while (low < high) {
while (low < high && a[high] >= tmp)
high--;
a[low] = a[high];
while (low < high && a[low] <= tmp)
low++;
a[high] = a[low];
}
a[low] = tmp;
return low;
}
}
3.插入排序(n^2)
从一开始第一个排好序,把要排序的数字保存下来,然后把前面大于它的向后挪一位,然后把保存下来的数赋值到该有的位置上.
#include<bits/stdc++.h>
using namespace std;
vector<int> a = {1, 110, 2, 7, 2, 1, 7, 9, 5, 8};
int sort() {
int flag = 1;
for(int i = 1, current,j; i < 10; i++) {
current = a[i];
for( j = i - 1; j >= 0 && a[j] > current; j--) {
a[j+1] = a[j];
}
a[j+1] = current;
}
}
int main() {
sort();
for(int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
}
4.归并排序(O(nlogn))
思想就是先分再合,先把一个数组分为一个一个组成的然后,不断地合并
合并的时候有四种情况:左边合并完了,右边合并完了,左边比右边小,右边比左边小
class Solution {
public static void main(String[] args) {
int[] nums = new int[]{1,5,7,4,6,9,-1,10,2};
Sort(nums,0,nums.length-1);
System.out.println(Arrays.toString(nums));
}
private static void Sort(int[] nums, int low, int high) {
if (low>=high) return;
int mid = low+(high-low)/2;
Sort(nums,low,mid);
Sort(nums,mid+1,high);
Merge(nums,low,mid,high);
}
private static void Merge(int[] nums, int low,int mid, int high) {
int a[] = nums.clone();
int k = low,i=low,j=mid+1;
while (k<=high){
if (i>mid){
nums[k++] = a[j++];
}else if(j>high){
nums[k++] = a[i++];
}else if (a[i]<a[j]){
nums[k++] = a[i++];
}else {
nums[k++] = a[j++];
}
}
}
}
5.堆排序(nlogn)
讲解:参考大佬https://www.cnblogs.com/Java3y/p/8639937.html
完全二叉树:除了最后一层,其它层都层都完全填充,所有节点保持左对齐
完全二叉树的特征:左子节点为父节点的2倍+1.右为2倍+2
最大堆:父节点的值大于子节点
在我的理解就是改进版的冒泡排序,只不过是找出最大值速度更快
#include<bits/stdc++.h>
using namespace std;
vector<int> a = {1, 110, 2, 7, 6, 5, 4, 8, 4, 1};
void Heapify(int cur, int size) {
if(cur < size) {
int left = cur * 2 + 1;
int right = cur * 2 + 2;
int max = cur;
if(left < size) {
if(a[left] > a[max]) {
max = left;
}
}
if(right < size) {
if(a[right] > a[max]) {
max = right;
}
}
if(cur != max) {
swap(a[max], a[cur]);
//这时的a[max]是换下来的小的值,再对他的子进行排序
Heapify(max, size);
}
}
}
void MaxHeap(int size) {
for(int i = size - 1; i >= 0; i--) {
//从下往上,先子后父
Heapify(i, size - 1);
}
}
int main() {
int n = a.size();
for(int i = 0; i < n; i++) {
//每一次都把最大的放在倒数第n-i个
MaxHeap(n - i);
swap(a[0], a[n - i - 1]);
}
for(int i = 0; i < a.size(); i++) {
cout << a[i] << " ";
}
}
5.希尔排序:
插入排序的升级版,先基本排好,最后再按插入排序排好
public class ShellSort {
public static int[] shellSort(int[] arr) {//遍历每一个gap//对每一个gap进行排序操作
int gap = arr.length/2;
for (;gap>0;gap/=2){
for (int j=0;j+gap<arr.length;j++){
for (int k=0;k+gap<arr.length;k+=gap){
if (arr[k]>arr[k+gap]){
int temp = arr[k];
arr[k] = arr[k+gap];
arr[k+gap] = temp;
}
}
}
}
return arr;
}
}
6.选择排序
比较好理解,把每次最小的放在前面
public class SelectSort {
public static int[] selectSort(int[] arr) {
for (int i=0;i<arr.length;i++){
int min = arr[i];
int mini = i;
for (int j=i+1;j<arr.length;j++){
if (arr[j]<min){
min = arr[j];
mini = j;
}
}
arr[mini] = arr[i];
arr[i] = min;
}
return arr;
}
}
