数据结构 - 排序(C++)

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

30

基本概念

  • 稳定性
    如果i==j,且i在j前面,排序完成后i仍旧在j前面则这个排序算法是稳定的,否则不稳定。

插入类排序

  • 直接插入排序
/**直接插入排序
时间复杂度:O(n^2)
空间复杂度:O(1) 
*/
void InsertSort(int R[], int n){int i, j;int temp;for(i=1; i=0 && temp
  • 直接选择排序
    在所有元素中选择出最小的,将元素位置与第一个交换,再将剩余元素重复上述过程,直至有序。

  • 折半插入排序

/**折半插入排序
时间复杂度:O(n^2)
空间复杂度:O(1) 
*/
void BinaryInsertSort(int R[], int n){int low, high, m;	int i, j, temp;for(i=1; i temp)high = m-1;elselow = m+1;}for(j=i-1; j>high; --j)	//将high后面的元素全部后移一位 R[j+1] = R[j];R[high+1] = temp;  		//插入元素 } 
}
  • 希尔排序
/**希尔排序 
时间复杂度:O(n^2)
空间复杂度:O(1) 
*/
void ShellSort(int R[], int n){int i, j, temp, k; int gap;	//gap为步长	 for(gap=n/2; gap>0; gap/= 2){	//将步长每次缩短一半 //对gap个子序列全部进行排序 for(i=0; i=0 && R[k]>temp){R[k+gap] = R[k];k -= gap;}R[k+gap] = temp;}}}}
}

交换类排序

  • 冒泡排序
/**冒泡排序
时间复杂度:O(n^2)
空间复杂度:O(1) 
*/
void BubbleSort(int R[], int n){int i, j, flag, temp;for(i=n-1; i>=1; --i){	//使下标为 i 的元素始终为最大值 flag = 0;			//标记变量 该趟是否发生了改变 for(j=1; j<=i; ++j){ if(R[j-1] > R[j]){	//交换元素 temp = R[j];R[j] = R[j-1];R[j-1] = temp;flag = 1;		//flag==1 证明该趟发生了交换  }}if(flag == 0)	//如果未发生交换代表序列有序 return;}
} 
  • 快速排序
/**快速排序
时间复杂度:O(n*log2^n)
空间复杂度:O(log2^n) 
*/
void QuickSort(int R[], int low, int high){int temp;int i=low, j=high;if(low < high){	temp = R[low];	//保存枢纽元素 //循环将元素分为 {小于枢纽 枢纽 大于枢纽} while(ii && R[j]>=temp) --j;	//从左往右扫描找到小于temp的元素 if(i
  • 堆排序
    先建堆,取堆顶,再重复。堆为一个完全二叉树。

算法比较

排序算法时间复杂度空间复杂度算法稳定性
直接插入排序O(n^2) 最坏、平均
O(n) 最好
O(1)稳定
折半插入排序O(n^2) 最坏、平均
O(n*log2^n) 最好
O(1)稳定
希尔排序O(n^2)O(1)不稳定
冒泡排序O(n^2) 最坏、平均
O(n) 最好
O(1)稳定
快速排序O(n^2) 最坏
O(n*log2^n)最好、平均
O(log2^n)不稳定
简单选择排序O(n^2)O(1)不稳定
堆排序O(n*log2^n)O(1)不稳定
二路归并排序O(n*log2^n)O(n)稳定
基数排序O(d(n+r_d)) 最坏、平均
n:序列关键字数
d:关键字的关键位数
r_d:关键字基的个数
O(r_d)稳定

稳定性:快速排序、希尔排序、简单选择排序、堆排序 是不稳定的,其余都是稳定的。