BubbleSort
用循环使数组元素按顺序两两比较
通过数值互换将比较大的逐渐向下沉
如果共有n个数，那么将进行n-1趟比较；
而第j趟比较将进行n-j次两两比较；
时间复杂度：O(n*n)
空间复杂度：O(1)
void BubbleSort(int ary[], int size)
{
for(int i = 0; i < size - 1; ++i) //共进行size-1趟比较
for(int j = 0; j < size - i - 1; ++j) //第i趟进行size-i次比较
if(ary[j] > ary[j+1])
swap(ary[j], ary[j + 1]);
}
SelectionSort
先将n个数中最小的数与a[0]对换；
再将a[1]~a[n-1]中最小的数与a[1]交换...
每比较一轮，找出未比较的数中最小的一个，共比较n-1轮；
时间复杂度：O(n*n)
空间复杂度：O(1)
void SelectionSort(int ary[], int size)
{
int i, j, k;
for(i = 0; i < size - 1; i++) //共进行size-1趟比较
{
k = i; //记录当前下标
for(j = i + 1; j < size; j++) //从当前元素的下个元素开始比较，1~size
if(ary[j] < ary[k])
k = j; //记录比当前元素小的元素的下标
if(k != i) //交换下标了才交换值，否则不交换
swap(ary[k], ary[i]);
//把k中存储的最小的数的下标，和a[i]对换
}
}
InsertionSort
为元素找到插入点，然后该点后面的元素依次后移，最后插入元素；
对于几乎排好序的数列，插入排序表现很好
可以用二分查找来优化寻找插入点的过程
时间复杂度：普通插入O(n*n)，二分插入O(nlgn)
空间复杂度：O(1)
普通插入
void InsertionSort(int ary[], int size)
{
for(int i = 1; i < size; ++i) //从第二个元素开始，到最后一个元素
{
int t = ary[i];
int j = i - 1;
while(j >= 0 && ary[j] > t)
{
ary[j + 1] = ary[j]; //逐个后移
--j;
}
ary[j + 1] = t; //插入到移出的缝隙中
}
}
二分插入
void InsertionSort(int ary[], int size)
{
for(int i = 1; i < size; ++i) //第二个元素到最后一个元素
{
int t = ary[i];
int low = 0, mid, high = i - 1; //注意high=i-1，这样就能保证low-high区间内是有序的
while(low <= high) //low才是ary[i]插入的正确位置
{ //循环的结果就是low=t下标-1，mid=t下标+1
mid = (high + low) / 2;
if(t < ary[mid])
high = mid - 1;
if(t > ary[mid])
low = mid + 1;
}
int j = i - 1; //j==high
while(j >= low)
{
ary[j + 1] = ary[j]; //逐个后移
--j;
}
ary[j + 1] = t; //插入到移出的缝隙中
}
}
MergeSort
归并排序采用分治法，将元素递归分成若干组，排好序后再逐级合并（Merge过程最坏情况下的比较次数为2n-1）
归并排序最好、最坏、平均复杂度都一样，比较占用空间，但却是稳定高效的排序算法，仅次于QuickSort
时间复杂度：O(nlgn)
空间复杂度：O(n)
stable：否
void Merge(int ary[], int low, int mid, int high)//前提是两个区间都是排好序的，low<=mid<high
{
int n1 =mid - low + 1; //左区间元素个数
int n2 = high - mid; //右区间元素个数
int *left = new int[n1];
int *right = new int[n2];
int i, j;
for(i = 0; i < n1; ++i)
left[i] = ary[low + i]; //将左区间的元素复制到left
for(j = 0; j < n2; ++j)
right[j] = ary[mid + j + 1]; //将右区间的元素复制到right
i = j = 0;
int k = low;
while(i < n1 && j < n2) //将left、right元素两两比较，小的放入原数组，大的不动
if(left[i] <= right[j])
ary[k++] = left[i++];
else
ary[k++] = right[j++];
while(i < n1) //如果有剩余的，则全部合并到原数组后面
ary[k++] = left[i++];
while(j < n2) //剩余的，肯定都是比前面大的
ary[k++] = right[j++];
delete []left;
delete []right;
}
void MergeSort(int ary[], int low, int high)
{
if(low < high) //只有一个元素时，认为是有序的，递归出口
{
int mid = (low + high) / 2; //将当前区间拆分成两半
MergeSort(ary, low, mid); //递归拆分左区间
MergeSort(ary, mid+1, high); //递归拆分右区间
Merge(ary, low, mid, high); //将当前两个排好序的区间合并
}
} //递归执行的顺序是，先递归将左区间拆分成只包含1个元素的小区间，再递归将右区间拆分成只包含1个元素的小区间，最后逐级合并
int main()
{
int a[10] = {7,5,0,9,3,6,8,2,4,1};
MergeSort(a, 0, 9);
for(int i = 0; i < 10; ++i)
cout<<a[i]<<' ';
return 0;
}
HeapSort
通过数据结构堆，来将插入排序和归并排序的优点结合起来，是一种渐进最优的排序
时间复杂度：O(nlgn)
空间复杂度：O(1)
stable：否
- （二叉）堆数据结构是一种数组对象，可以被视为一颗完全二叉树
- 对于从0开始的数组，给定一个结点下标i，其父结点的下标为(i-1)/2，左子树的下标为i2+1，右子树的下标为i2+2
- 可以通过左移/右移1位再+1/-1的方法来快速计算出父/子结点
- 二叉堆有两种：
- 最大堆：某个结点的值至多和其父结点的值一样大；这样，堆中的最大元素就存储在根结点中
- 最小堆：和最大堆正相反
在堆排序算法中使用最大堆，在优先级队列中使用最小堆
- 堆可以被视为一棵树：
- 结点在树中的高度：从本结点到叶子的最长简单下降路径上结点的数目；因为具有n个元素的堆是基于一棵完全二叉树的，因此其高度为lgn
- 结点在树中的深度：从本结点到根结点的最长简单上升路径上结点的数目
- 因为二叉堆的性质，数组的后二分之一元素都是叶子
- 在一个含有n个元素的二叉堆中，至多有n/(2的h次幂)个高度为h的结点（叶子高度为1）
- 完全二叉树：
所有叶子都在同一层且并不是满的，缺少右边的叶子（如果缺少的叶子的右边还有叶子，那么就不是完全二叉树）
满二叉树：
国内定义：
所有叶子都在同一层且刚好是满的
国外定义：
所有结点，要么没有子结点（指叶子），要么有两个子结点
满二叉树是完全二叉树的一个特例 - 先级队列： 堆的一个很常见的应用： 作为高效的优先级队列；像堆一样，优先级队列也分为两种：最大优先级队列和最小优先级队列 最大优先级队列的一个应用是分时计算机上进行作业调度；这种队列对要执行的各作业及它们之间的优先关系先加以记录，当上一个作业完成时，从所有等待的作业中，选择出具有最高优先级的作业执行 最小优先级队列的一个应用是基于事件驱动的模拟器中，每一个都有时间做为其关键字；事件模拟要按时间的发生顺序进行，最小优先级队列比较合适
- 先级队列返回并去掉其根结点后，将数组最后一个元素交换到原根结点位置，而不是所有元素都移动
void maxHeapify(int ary[], int heapSize, int index)
{
int left = 2 * index + 1; //此函数是有前提的：以left和right为根的子树是最大堆
int right = 2 * index + 2;
int largest = index;
if(left <= heapSize - 1 && ary[left] > ary[largest])
largest = left;
if(right <= heapSize - 1 && ary[right] > ary[largest])
largest = right;
if(largest != index) //largest是leftchild和rightchild中最大的
{
swap(ary[index], ary[largest]);
maxHeapify(ary, heapSize, largest);
} //将父结点交换到子结点后，继续检查该结点的子结点是否符合最大堆
}
void BuildmaxHeap(int ary[], int heapSize) //构建最大堆
{ //因为后二分之一都是叶子没有子结点，所以从heapSize/2开始
for(int i = (heapSize - 1)/2; i >= 0; --i)
maxHeapify(ary, heapSize, i); //从叶子到根结点
}
void HeapSort(int ary[], int heapSize)
{
BuildmaxHeap(ary, heapSize);
for(int i = heapSize - 1; i > 0; --i)
{
swap(ary[0], ary[i]);
maxHeapify(ary, i, 0); //堆大小逐渐减小，去掉最后面的排好序的元素
}
}
int main()
{
int a[10] = {7, 5, 0, 9, 3, 6, 8, 2, 4, 1};
HeapSort(a, 10);
for(int i = 0; i < 10; ++i)
cout<<a[i]<<' ';
return 0;
}
QuickSort
快速排序是采用分治法的就地排序，最坏运行时间为O(nn)，虽然最坏运行时间比较差，但快速排序仍然是排序的最佳实用选择，因为其平均性能相当好：期望时间复杂度为O(nlgn)，且O(nlgn)中的常数因子很小 快速排序的运行时间与划分是否对称有关，而后者又与选择了哪个元素来进行划分有关；如果划分是对称的，则与合并算法一样快；如果不对称就与插入排序一样慢 时间复杂度：平均O(nlgn)，最坏O(nn) 空间复杂度：O(1) stable：否 int Partition(int ary[], int left, int right) { int i = left - 1; //i的起始位置在left和j的前一位 for(int j = left; j < right; ++j) if(ary[j] <= ary[right]) //主元设为当前区间最后一个元素,pivot=ary[right] { ++i; swap(ary[i], ary[j]); } swap(ary[i + 1], ary[right]); //将主元从最后交换到i的下一位 //因为0~i都是小于主元的 //所以交换后主元的位置已经是排好序的位置 return i + 1; //返回当前主元的位置 } void QuickSort(int ary[], int left, int right) { if(left < right) { int pivot = Partition(ary, left, right); QuickSort(ary, left, pivot - 1); //因为主元位置已排好，所以跳过上次主元位置 QuickSort(ary, pivot + 1, right); } } int main() { int a[10] = {7, 8, 0, 9, 3, 6, 1, 2, 4, 5}; QuickSort(a, 0, 9); //数组名，最小下标，最大下标 for(int i = 0; i < 10; ++i) cout<<a[i]<<' '; return 0; }
void QuickSort(int ary[], int left, int right) //尾递归 { while(left < right) //if改成while { int pivot = Partition(ary, left, right); QuickSort(ary, left, pivot - 1); //先一直执行本句至底，回推只执行本句和下句 left = pivot + 1; //在回推过程中将left=pivot+1代入上句的left } }
void QuickSort(int ary[], int left, int right) //尾递归优化，栈深度为O(lgn)，时间复杂度不变 { while(left < right) //if改成while { int pivot = Partition(ary, left, right); if(pivot - left < right - pivot) { QuickSort(ary, left, pivot - 1); left = pivot + 1; } else { QuickSort(ary, pivot + 1, right); right = pivot - 1; } } } ==============================以上是比较排序，以下是线性时间排序============================== CountingSort 计数排序是通过外设一个数组，以所排列的元素的值做为数组的下标来记录所有等于该值的元素的个数，最后根据需求正反输出 特别适用于元素值之间跨度不大的数组的排序（如果元素值之间跨度不大、但元素值特别大的情况可以通过所有元素减去某统一值的方法来削减空间开销） 时间复杂度：O(n) 空间复杂度：O(x) //x为元素中最大的数 void CountingSort(int ary[], int size, int max) //算法导论上的 { int temp = new int[max]; int result = new int[size]; memset(temp, 0, max * 4); for(int i = 0; i < size; ++i) ++temp[ary[i]]; for(int i = 1; i < max; ++i) temp[i] += temp[i - 1];//将等于i的元素的个数加上等于i-1的元素的个数,此循环结束后， //temp[i]存储的就是i在结果中的位置 for(int i = size - 1; i >= 0; --i)//一定要降序，否则排序会失去稳定性，此处的稳定性是指： { //对于相同值的元素，彼此的相对位置是不变的 //即在原始数组中先出现的，在结果中也一定先出现 //这一点对包含在基数排序中的计数排序来说是必须的 result[temp[ary[i]] - 1] = ary[i];//temp[ary[i]]-1就是ary[i]在结果中位置的下标 --temp[ary[i]]; //如果有相同元素，则让该元素在结果中的位置向前移动一位 } //以免其他相同值的元素都落在同一下标上 for(int i = 0; i < size; ++i) //将结果复制进原数组 ary[i] = result[i]; delete []temp; delete []result; } void CountingSort(int ary[], int size, int max) //自己写的，不稳定 { int temp = new int[max]; memset(temp, 0, max * 4); for(int i = 0; i < size; ++i) ++temp[ary[i]]; for(int i = 0, j = 0; i < max; ++i) //虽然嵌套了，但实际复杂度应该也为O(n) if(temp[i]) for(int k = 0; k < temp[i]; ++k) ary[j++] = i; delete []temp; } int main() { int a[10] = {7, 8, 0, 9, 3, 6, 4, 2, 1, 5}; CountingSort(a, 10, 10); for(int i = 0; i < 10; ++i) cout<<a[i]<<' '; return 0; }
RadixSort
基数排序是通过先排序元素的最低有效数字再逐位排序直到最高有效数字来排序的，也就是按照元素每个数位上的数来排序，且顺序是从最低位向最高位；如果元素的位数不同的话，在较短的元素的前面加0来统一位数
关于此算法，很重要的一点就是按位排序的算法要“稳定”：
对于相同值的元素，彼此的相对位置是不变的
即在原始数组中先出现的，在结果中也一定先出现
每位上的数字稳定为0~9，所以计数排序（而且是稳定的）尤其合适作为基数排序中的按位排序
在一台典型的顺序存取计算机上，有时采用基数排序来对有多个关键字域的记录进行排序，比如日期：年、月、日
给定n个d位数，每一位可以取k种可能的值，基数排序算法能以O(d(n+k))的时间正确的对这些数排序
给定n个b位数以及任何r<=b，基数排序能在O((b/r)(n+2^r))时间正确的对这些数排序
时间复杂度：O(n)
空间复杂度：O(x) //x为某一位中最大的数
void RadixSort(int ary[],int digit,int size,int max)
{
int result=new int[size];
int temp=new int[max];
int radix=1;
int t;
for (int i=0;i
5、最坏情况为线性时间的选择：
int SelectPartition(int ary[],int left,int right,int pivot)
{
int i=left-1,j;
for(j=left;j<=right;++j)
if(ary[j]==pivot) //找到pivot的下标
break;
swap(ary[j],ary[right]);
for(j=left;j
r[0]=r[i]; //暂存被插入记录
for (j=i-d; j>0 && r[0]
int i=first; //初始化
int j=end;
int temp;
while (i<j)
{
while (i<j && r[i]<= r[j])
j--; //右侧扫描
if (i<j)
{
temp=r[i]; //将较小记录交换到前面
r[i]=r[j];
r[j]=temp;
i++;
}
while (i<j && r[i]<= r[j])
i++; //左侧扫描
if (i<j)
{
temp=r[j];
r[j]=r[i];
r[i]=temp; //将较大记录交换到后面
j--;
}
}
return i; //i为轴值记录的最终位置
}
//快速排序
void QuickSort(int r[], int first, int end)
{
if (first<end)
{ //递归结束
int pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}
//简单选择排序
void SelectSort(int r[ ], int n)
{
int i;
int j;
int index;
int temp;
for (i=0; i<n-1; i++) //对n个记录进行n-1趟简单选择排序
{
index=i;
for (j=i+1; j<n; j++) //在无序区中选取最小记录
if (r[j]<r[index])
index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<"\n";
}
//筛选法调整堆
void Sift(int r[], int k, int m)
{
int i;
int j;
int temp;
i=k;
j=2*i+1; //置i为要筛的结点，j为i的左孩子
while (j<=m) //筛选还没有进行到叶子
{
if (j<m && r[j]<r[j+1])
j++; //比较i的左右孩子，j为较大者
if (r[i]>r[j]) break; //根结点已经大于左右孩子中的较大者
else
{
temp=r[i];
r[i]=r[j];
r[j]=temp; //将根结点与结点j交换
i=j;
j=2*i+1; //被筛结点位于原来结点j的位置
}
}
} //堆排序 void HeapSort(int r[ ], int n) {
int i;
int temp;
for (i=n/2; i>=0; i--) //初始建堆，从最后一个非终端结点至根结点
Sift(r, i, n) ;
for (i=n-1; i>0; i--) //重复执行移走堆顶及重建堆的操作
{
temp=r[i];
r[i]=r[0];
r[0]=temp;
Sift(r, 0, i-1);
}
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<"\n";
} //一次归并 void Merge(int r[], int r1[], int s, int m, int t) { int i=s; int j=m+1; int k=s;
while (i<=m && j<=t)
{
if (r[i]<=r[j])
r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k]
else
r1[k++]=r[j++];
}
if (i<=m)
while (i<=m) //若第一个子序列没处理完，则进行收尾处理
r1[k++]=r[i++];
else
while (j<=t) //若第二个子序列没处理完，则进行收尾处理
r1[k++]=r[j++];
} //一趟归并 void MergePass(int r[ ], int r1[ ], int n, int h) { int i=0; int k; while (i<=n-2h) //待归并记录至少有两个长度为h的子序列 { Merge(r, r1, i, i+h-1, i+2h-1); i+=2h; } if (i<n-h) Merge(r, r1, i, i+h-1, n); //待归并序列中有一个长度小于h else for(k=i; k<=n; k++) //待归并序列中只剩一个子序列 r1[k]=r[k]; } //归并排序的非递归算法 void MergeSort1(int r[ ], int r1[ ], int n ) { int h=1; int i; while (h<n) { MergePass(r, r1, n-1, h); //归并 h=2h; MergePass(r1, r, n-1, h); h=2*h; } for(i=0;i<n;i++) cout<<r[i]<<" "; cout<<"\n"; } //归并排序的递归算法 void MergeSort2(int r[], int r1[], int r2[],int s, int t) {
int m;
if (s==t)
{
r1[s]=r[s];
}
else
{
m=(s+t)/2;
MergeSort2(r, r2, r1, s, m); //归并排序前半个子序列
MergeSort2(r, r2, r1, m+1, t); //归并排序后半个子序列
Merge(r2, r1, s, m, t); //将两个已排序的子序列归并
}
}
以上来自 QQ群: C++/Python/Qt技术交流 大佬
Icy
