数据结构之排序
目录
归并排序：
堆排序：
快速排序：
归并排序：
归并排序采用分治法，将元素递归分成若干组，排好序后再逐级合并（Merge过程最坏情况下的比较次数为2n-1）归并排序最好、最坏、平均复杂度都一样，比较占用空间，但却是稳定高效的排序算法，仅次于QuickSort时间复杂度：O(nlgn)空间复杂度：O(n)stable：是
void merge(int *array, int first, int center, int end)
{
int n1 = center - first + 1;
int n2 = end - center;
int *L = new int[1 + n1]; //用动态数组储存，不然会出错的
int *R = new int[1 + n2];
int i, j;
for (i = 0; i < n1; i++)
{
L[i] = array[first + i];
}
for (j = 0; j < n2; j++)
{
R[j] = array[center + j + 1];
}
L[n1] = INT_MAX; //设置哨兵的判断一个结束后，剩余全部放入。
R[n2] = INT_MAX;
i = j = 0;
for (int k = first; k <= end; ++k)
{
if (L[i] < R[j])
{
array[k] = L[i];
i++;
}
else
{
array[k] = R[j];
j++;
}
}
}
void merge_sort(int array[], int first, int end)
{
if (first < end)
{
int center = (first + end) / 2;
merge_sort(array, first, center);
merge_sort(array, center + 1, end);
merge(array, first, center, end);
}
}
void testMergeSort()
{
int array[10] = { 0,6,1,2,4,7,8,9,3,5 };
cout << "arr is old :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
merge_sort(array, 0, 9); //排序后
cout << "arr is new :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
结果：
结果：
arr is old :0 6 1 2 4 7 8 9 3 5
arr is new :0 1 2 3 4 5 6 7 8 9
堆排序：
通过数据结构堆，来将插入排序和归并排序的优点结合起来，是一种渐进最优的排序时间复杂度：O(nlgn)空间复杂度：O(1)stable：否
0、（二叉）堆数据结构是一种数组对象，可以被视为一颗完全二叉树 1、对于从0开始的数组，给定一个结点下标i，其父结点的下标为(i-1)/2，左子树的下标为i*2+1，右子树的下标为i*2+2 2、可以通过左移/右移1位再+1/-1的方法来快速计算出父/子结点 3、二叉堆有两种，最大堆和最小堆 最大堆：某个结点的值至多和其父结点的值一样大；这样，堆中的最大元素就存储在根结点中 最小堆：和最大堆正相反 在堆排序算法中使用最大堆，在优先级队列中使用最小堆 4、堆可以被视为一棵树： 结点在树中的高度：从本结点到叶子的最长简单下降路径上结点的数目；因为具有n个元素的堆是基于一棵完全二叉树的，因此其高度为lgn 结点在树中的深度：从本结点到根结点的最长简单上升路径上结点的数目 5、因为二叉堆的性质，数组的后二分之一元素都是叶子 6、在一个含有n个元素的二叉堆中，至多有n/(2的h次幂)个高度为h的结点（叶子高度为1） 7、完全二叉树： 所有叶子都在同一层且并不是满的，缺少右边的叶子（如果缺少的叶子的右边还有叶子，那么就不是完全二叉树） 满二叉树： 国内定义： 所有叶子都在同一层且刚好是满的 国外定义： 所有结点，要么没有子结点（指叶子），要么有两个子结点 满二叉树是完全二叉树的一个特例 --------------------------- 8、优先级队列： 堆的一个很常见的应用： 作为高效的优先级队列；像堆一样，优先级队列也分为两种：最大优先级队列和最小优先级队列 最大优先级队列的一个应用是分时计算机上进行作业调度；这种队列对要执行的各作业及它们之间的优先关系先加以记录，当上一个作业完成时，从所有等待的作业中，选择出具有最高优先级的作业执行 最小优先级队列的一个应用是基于事件驱动的模拟器中，每一个都有时间做为其关键字；事件模拟要按时间的发生顺序进行，最小优先级队列比较合适 9、优先级队列返回并去掉其根结点后，将数组最后一个元素交换到原根结点位置，而不是所有元素都移动
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); //堆大小逐渐减小，去掉最后面的排好序的元素
}
}
void testHeapSort()
{
int array[10] = { 0,6,1,2,4,7,8,9,3,5 };
cout << "arr is old :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
HeapSort(array, 10); //排序后
cout << "arr is new :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
结果：
结果：
arr is old :0 6 1 2 4 7 8 9 3 5
arr is new :0 1 2 3 4 5 6 7 8 9
快速排序：
快速排序是采用分治法的就地排序，最坏运行时间为O(n*n)，虽然最坏运行时间比较差，但快速排序仍然是排序的最佳实用选择，因为其平均性能相当好：期望时间复杂度为O(nlgn)，且O(nlgn)中的常数因子很小快速排序的运行时间与划分是否对称有关，而后者又与选择了哪个元素来进行划分有关；如果划分是对称的，则与合并算法一样快；如果不对称就与插入排序一样慢时间复杂度：平均O(nlgn)，最坏O(n*n)空间复杂度：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);
}
}
void testQuickSort()
{
int array[10] = { 0,6,1,2,4,7,8,9,3,5 };
cout << "arr is old :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
QuickSort(array,0, 9); //排序后
cout << "arr is new :";
for (int i = 0; i < 10; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
测试结果：
结果：
arr is old :0 6 1 2 4 7 8 9 3 5
arr is new :0 1 2 3 4 5 6 7 8 9
