快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。递归地排序两个子序列，直至最小的子序列长度为0或者1，整个递归过程结束，详细步骤为：
- 挑选基准值: 从数列中挑出一个元素称为基准pivot，选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
- 基准值分割: 重新排序数列，所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面，与基准值相等的数可以到任何一边,在这个分割结束之后，对基准值的排序就已经完成。
- 递归子序列: 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序，步骤同上两步骤,递归终止条件是序列大小是0或1，因为此时该数列显然已经有序。
#include <stdio.h>
void exchange(int *p, int *q)
{
int temp = *p;
*p = *q;
*q = temp;
}
int quickSort(int arr[],int left, int right)
{
if (left >= right)
{
return 0;
}
int i, j, temp;
temp = arr[left];
i = left;
j = right;
while (i != j)
{
while (i < j && arr[j] >= temp)
{
j--;
}
exchange(&arr[i], &arr[j]);
while (i < j && arr[i] <= temp)
{
i++;
}
exchange(&arr[i], &arr[j]);
}
quickSort(arr,i + 1, right);
quickSort(arr,left, i - 1);
return 1;
}
int main()
{
int arr[9] = { 5,1,4,6,7,4,3,5,11 };
quickSort(arr,0, 8);
for (int i = 0; i <= 8; i++)
{
printf("%d ", arr[i]);
}
system("PAUSE");
return 0;
}
堆排序：
#include <iostream>
#include <algorithm>
using namespace std;
void sink(int a[],int index,int n)
{
int leftchild = 2*index + 1;//左节点下标
int rightchild = 2*index +2;//右结点下标
int present = index;//要调整的节点下标
//下沉左边
if(leftchild < n && a[leftchild] > a[present])
{
present = leftchild;
}
//下沉右边
if(rightchild < n && a[rightchild] > a[present])
{
present = rightchild;
}
//如果下标不相等，证明被调换过了
if(present != index)
{
int temp = a[index];
a[index] = a[present];
a[present] = temp;
//继续下沉
sink(a, present,n);
}
}
void buildheap(int a[],int n)
{
//堆是完全二叉树
for(int i = n/2; i >= 0; i--)
{
sink(a,i,n);
}
}
void sort(int a[],int n)
{
//构建堆
buildheap(a,n);
for(int i = n - 1; i>0; i--)
{
//将堆顶元素与末位元素调换
int temp = a[0];
a[0] = a[i];
a[i] = temp;
n--;//数组长度-1 隐藏堆尾元素
sink(a,0,n);//将堆顶元素下沉 目的是将最大的元素浮到堆顶来
}
}
int main()
{
int data[8] = {4,6,3,2,1,5,8,0};
int size = sizeof(data)/sizeof(int);
sort(data,size);
for(int i = 0; i < size; i++)
{
std::cout << data[i] << " ";
}
cout << endl;
return 0;
}
本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为:
2020/05/09 15:35