交换排序
冒泡排序
过程略
时间复杂度O(n^2)
空间复杂度O(1)
优化
1.添加一个标志，标识当前轮是否数组有序，如果有则结束冒泡
2.判断部分有序：前一趟冒泡排序中最后一次发生交换的地方作为下一次冒泡的终点
快速排序
选择一个基准（放在排序后数组正确位置的元素），（第一个/最后一个/中间一个/随机一个）。关键在于做一个划分，每一次划分都将基准x放到正确的位置，将所有比x小的放在左边，比x大的放在右边。
复杂度：O(nlogn)
注：如果是一个有序数组，出现最坏情况
#include<stdio.h>
#include<stdlib.h>
void QuickSort(int arr[], int low, int high)
{
if(low<high)
{
int i=low;
int j=high;
int k = arr[low];
while(i<j)
{
while(i<j && arr[j] >=k)
{
j--;
}
if(i<j)
arr[i++]=arr[j];
while(i<j && arr[i] <k)
{
i++;
}
if(i<j)
arr[j--] = arr[i];
}
arr[i] = k;
QuickSort(arr,low,i-1);
QuickSort(arr,i+1,high);
}
}
|