排序算法基础、改进综合

排序算法基础、改进综合： //冒泡排序 //定向冒泡[鸡尾酒]排序 //选择排序 //改进的选择排序 //直接插入排序 //二分插入排序 //希尔排序 //自顶向下地归并排序 //自底向上地归并排序 //堆排序 //快速排序 //改进的快速排序：三向切分快速排序

#include“SeqHeap.h“

template
SeqHeap::SeqHeap（）
{
	size = 0;
}

template
SeqHeap::SeqHeap（DataType arr[] int n）
{
	for （int i = 0; i < n; i++） {
		heap[i+1]=arr[i];
	}
	size = n;
}

template
SeqHeap::~SeqHeap（）
{
}

template
void SeqHeap::MakeMaxSeqHeap（SeqHeap *h）
{
	h->MaxHeapSort（h）;//构建最大顶堆
}

template
void SeqHeap::MakeMinSeqHeap（SeqHeap *h）
{
	h->MinHeapSort（h）;//构建最小顶堆
}

template
void SeqHeap::PrintSeqHeap（SeqHeap h）
{
	for （int i = 1; i <= size; i++） {
		cout << h.heap[i] << “ “;
		if （i%20 == 0）
			cout << endl;
	}
	cout << endl;
}

template
void SeqHeap::MaxHeapSort（SeqHeap * h）
{
	int N = h->size;
	for （int k = N / 2; k >= 1; k--） {
		SinkConversely（h->heap k N）;//此步是堆的构造：构造的结果是部分堆有序，即头结点的值是最小的。
	}
	while （N > 1）
	{
		Swap（h->heap 1 N--）;
		SinkConversely（h->heap 1 N）;
	}
}

template
void SeqHeap::MinHeapSort（SeqHeap *h）
{
	int N = h->size;
	for （int k = N / 2; k >= 1; k--） {
		Sink（h->heap k N）;//此步是堆的构造：构造的结果是部分堆有序，即头结点的值是最大的。
	}
	while （N > 1）
	{
		Swap（h->heap 1 N--）;
		Sink（h->heap 1 N）;
	}
}

/*
  arr[]：即 h->heap
      k：把位置为k的结点下沉
        【该结点的特点：heap[k] < heap[2*k] （OR||AND） heap[k]      N：堆里（即heap[]）有N个元素，即 h->size的值
*/
template
void SeqHeap::Sink（DataType arr[] int k int N）
{
	while （2*k <= N） //当结点k 的子结点2*k 不超过当前数组元素的最大下标时【结点 2*k 是 结点 k 的子结点】，才有机会继续下沉
	{
		int j = 2 * k;
		if （j < N && Less（arr[j] arr[j + 1]））
			j++;
		if （Less（arr[j] arr[k]）） break;//also could be !Less（arr[k] arr[j]）即当 arr[k]>arr[j]时跳出循环体
		Swap（arr k j）;
		k = j;
	}
}

/*
  arr[]：即 h->heap
      k：把位置为k的结点上浮【该结点的特点：heap[k] > heap[k/2]，即该结点值比其父结点值大 】
      N：堆里（即heap[]）有N个元素，即 h->size的值
*/
template
void SeqHeap::Swin（DataType arr[] int k int N）
{
	while （ k>1 && Less（arr[k/2]arr[k]） ）//若结点 k 不是根结点、且其值比其父结点大时，循环体进行，结点k上浮
	{
		Swap（arr k / 2 k）;
		k = k / 2;
	}
}

template
void SeqHeap::SinkConversely（DataType arr[] int k int N）
{
	while （2 * k <= N） //当结点k 的子结点2*k 不超过当前数组元素的最大下标时【结点 2*k 是 结点 k 的子结点】，才有机会继续下沉
	{
		int j = 2 * k;
		if （j < N && Less（arr[j + 1] arr[j]））
			j++;
		if （Less（arr[k] arr[j]）） break;//also could be !Less（arr[k] arr[j]）即当 arr[k]		Swap（arr k j）;
		k = j;
	}
}

template
void SeqHeap::SwinConversely（DataType arr[] int k int N）
{
	while （k>1 && Less（arr[k / 2] arr[k]））//若结点 k 不是根结点、且其值比其父结点小时，循环体进行，结点k上浮
	{
		Swap（arr k / 2 k）;
		k = k / 2;
	}
}

template
void SeqHeap::Swap（DataType arr[] int i int j）
{
	DataType temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

template


 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       9491  2019-03-08 00:30  SortAlgorithm.h

     文件       3744  2019-03-08 00:30  SeqHeap.cpp

     文件      10463  2019-03-06 17:06  SortAlgorithm.cpp

     文件      17303  2019-03-08 00:31  SortAlgorithmTest.cpp

     文件       2018  2019-03-08 00:30  SeqHeap.h

----------- ---------  ---------- -----  ----

                43019                    5