#算法的稳定性：
存在多个具有相同排序码的记录，排序后这些记录的相对次序保持不变
#理想的空间效率：
算法执行期间所需要的辅助空间与待排序的顺序无关
插入排序
//直接插入排序
void InsertSort(int A[],int n)
{
int i,j,temp;
for( i=1; i
temp=A[i]; //用temp暂存A[i]
for(j=i-1;j>=0 && A[j]>temp;–j) //检查所有前面已排好序的元素
A[j+1]=A[j]; //所有大于temp的元素都向后挪位
A[j+1]=temp; //复制到插入位置
}
}
templatevoid InsertSort(T* array, int n) { //array待排序数组,n:数组元素数量 int i, j; //循环变量 T temp; //存储待排序元素 for (i = 1; i < n; i++) { //将各个元素插入已经排好的序列中 j = i; temp = array[i]; //待排序元素赋值给临时变量 while (j > 0 && temp < array[j - 1]) { //当未达到数组的第一个元素或者待插入元素小于当前元素 array[j] = array[j - 1]; //就将该元素后移 j--; //下标减一，继续比较 } array[j] = temp; //插入位置已经找到，立即插入 } }
空间代价：o(1)
最佳情况：n-1次比较 2（n-1) 次移动
最差情况：n(n-1)/2 (n-1)(n+4)/2
平均情况： (n-1)(n)/4 个逆序对 o(n2)
/直接插入排序（带哨兵)
void InsertSort(int A[],int n)
{
int i,j;
for( i=2 ; i<=n; i++) //依次将A[2]~A[n]插入到前面已排序序列
if(A[i]
A[0]=A[i]; //复制为哨兵，A[0]不存放元素
for(j=i-1;A[0]
空间复杂度：O(1)
最好时间复杂度—— O(n)
最坏时间复杂度——O(n 2 )
平均时间复杂度：O(n 2 )
算法稳定性：稳定
//没讲：折半插入排序
void BinaryInsertSort(int R[],int n) {
int i, j, low, mid, high, temp;
for(i = 1; i < n; i++) {
low = 0;
high = i - 1;
temp = R[i];
while(low <= high) {//找到合适的插入位置high+1，如果中间位置元素比要插入元素大，则查找区域向低半区移动，否则向高半区移动
mid = (low + high) / 2;
if(R[mid] > temp)
high = mid - 1;
else
low = mid + 1;
}
for(j = i-1; j >= high+1; j--) {//high+1后的元素后移
R[j+1] = R[j];
}
R[j+1] = temp; //将元素插入到指定位置
}
}
最坏情况（整个序列逆序时）时间复杂度为O(n2)
最优情况（整个序列初始顺序，从大到小时）时间复杂度为O(nlog2n)
平均情况时间复杂度为O(n2)
void shellSort(int a[], int n) {//对a[1]~a[n]进行排序
int d, i, j;
for (d = n / 2; d >= 1; d /= 2) {//d依次除以2
for (i = d + 1; i <= n; ++i) {
if (a[i] < a[i - d]) {
a[0] = a[i];//a[0]作为暂存单元
for (j = i - d; j >= 1 && a[0] < a[j]; j -= d) { //直接插入排序，后移操作
a[j + d] = a[j];
}
a[j + d] = a[0];//j-d+d=j
}
}
}
}
o(n 2) 时间开销o(1)
void sort(int x[],int n)
{//冒泡排序
int i,l,t;
for(i=0;ix[l+1])
{
t=x[l];
x[l]=x[l+1];
x[l+1]=t;
}
}
void Swap(int arr[], int i, int j)
{
int temp=arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void BubbleSort(int arr[], int n) {
for (int i=0;i
for(int j=0;j
if(arr[j]>arr[j+1]) //如果条件改为arr[j] >= arr[j+1] 则变为不稳定的排序算法
{
Swap(arr, j, j + 1);
}
}
}
}
冒泡排序
- 最差时间复杂度 O(n^2)
- 最优时间复杂度 O(n)
- 平均时间复杂度 O(n^2)
- 空间复杂度 O(1)
- 稳定性 稳定
void SelectSort(ElemType A[], int n) {
for (int i = 0; i < n - 1; i++) {//一共进行n-1趟
int min_p = i;//记录最小元素位置
for (int j = i + 1; j < n; j++)//在A[i...n-1]中选择最小的元素
if (A[i] < A[min_p]) min_p = j;//更新最小元素位置
if (min_p != i) swap(A[i], A[min_p]);//封装的swap()函数共移动元素3次
}
}
直接选择排序 比较次数n(n-1)/2 o(n)
交换次数：n-1
堆排序：
void down(int low, int high) {
int i = low, j = i * 2;
while (j<=high) {
if(heap[j]
swap(heap[j], heap[i]);
i = j;
j = i * 2;
} else {
break;
}
}
}
void createheap(int n){
for(int i=n/2;i>=1;i--){
down(i,n);
}
}
void heapsort(int n){
createheap(n);
for(int i=n;i>1;i--){
swap(heap[i], heap[1]);
down(1,i-1);
}
}
快速排序：
书本：
int partition(int a[], int left, int right){
int l = left; int r = right; int temp = a[r];
while (l!=r)
{
while (a[l] <= temp && r>l){
l++;
}
if (l
a[r] = a[l];
r--;
}
while (a[r] >= temp && r>l){
r--;
}
if (l
a[l] = a[r];
l++;
}
}
a[l] = temp;
return l;
}
void quick_sort(int a[], int left, int right)
{
if (left >= right){
return;
}
int pivot = left;
swap(a[pivot], a[right]);
pivot = partition(a, left, right);
quick_sort(a, left, pivot - 1);
quick_sort(a, pivot + 1, right);
}
其他教材：
//用第一个元素将待排序序列划分为左右两个部分
int Partiton(int a[], int low, int high) { //划分
int temp = a[low]; //第一个元素作为一个枢轴
while (low < high) { //low和high搜索枢轴的最终位置
while (low < high && a[high] >= temp) high--;
a[low] = a[high]; //比较枢轴小的元素移动到左端
while (low < high && a[low] <= temp) low++;
a[high] = a[low]; //比较枢轴大的元素移动到右端
}
a[low] = temp; //枢轴元素存放在最终位置
return low; //返回存放枢轴的最终位置
}
void QuickSort(int a[], int low, int high) { //排序
if (low < high) { //递归跳出的条件
int pivot = Partiton(a, low, high);
QuickSort(a, low, pivot - 1); //划分左子表
QuickSort(a, pivot + 1, high); //划分右子表
}
优化版：
void InsertSort(int A[],int n)
{
int i,j,temp;
for( i=1; i
temp=A[i]; //用temp暂存A[i]
for(j=i-1;j>=0 && A[j]>temp;–j) //检查所有前面已排好序的元素
A[j+1]=A[j]; //所有大于temp的元素都向后挪位
A[j+1]=temp; //复制到插入位置
}
int partition(int a[], int left, int right){
int l = left; int r = right; int temp = a[r];
while (l!=r)
{
while (a[l] <= temp && r>l){
l++;
}
if (l
a[r] = a[l];
r--;
}
while (a[r] >= temp && r>l){
r--;
}
if (l
a[l] = a[r];
l++;
}
}
a[l] = temp;
return l;
}
void modquicksort(int * array,int left,int right){
if(right-left+1>28){
int pivot=array[left];
swap(array[pivot],array[right]);
pivot=partition(array,left,right);
modquicksort(array,left,pivot-1);
modquicksort(array,pivot+1,right);
}
void quicksort(int *array,int n){
modquicksort(array,0,n-1);
InsertSort(array,n);
}
归并排序
int *B=(int *)malloc( n*sizeof(int)); //辅助数组B
//A[ low...mid]和A[mid+...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high)
{
int i,j,k;
for( k=low ; k<=high;k++)
B[k]=A[k]; //将A中所有元素复制到B中
for( i=low , j=mid+1,k=i; i<=mid&&j<=high ;k++) //归并
{
if(B[i]<=B[j])
A[k]=B[i++]; //将较小值复制到A中
else
A[k]=B[j++];
}
while( i<=mid)A[k++]=B[i++];
while(j<=high)A[k++]=B[j++];
}
void MergeSort(int A[] ,int low,int high)
{
if (low
int mid=(low+high)/2; //从中间划分
MergeSort(A,low,mid); //对左半部分归并排序
MergeSort(A,mid+1,high); //对右半部分归并排序
Merge(A,low,mid,high); //归并
}
}
空间开销：o(n)
时间复杂度：o(nlogn)
也有优化版的 和快排一样
桶排序
从右开始
void BucketSort(int array[],int n,int max){
int * tempArray=new int[n];
int *count=new int[max];
int i;
for(i=0;i=0;i--)
array[--count[tempArray[i]]]=tempArray[i];
}
时间复杂度 空间开销都为o(m+n)
基数排序
r为基数 d为排序码数
void RadixSort(int array[],int n,int d,int r){
int *tempArray=new int[n];
int * count=new int [r];
int i,j,k;
int Radix=1;
for(i=1;i<=d;i++){
for(j=0;j
count[j]=0;
}
for(j=0;j
k=(array[j]/Radix)%r;
count[k]++;
}
for(j=1;j
count[j]=count[j-1]+count[j];
}
for(j=n-1;j>=0;j--){
k=(array[j]/Radix)%r;
tempArray[--count[k]]=array[j];
}
for(j=0;j
array[j]=tempArray[j];
}
Radix*=r;
}
}
o(d(n+r))
