接下来的几篇博客都是关于排序的;主要有插入类排序;交换类排序;选择类排序;
插入类排序主要有直接插入如排序(straight insertion sort);折半插入排序(bianry insertion sort); Shell sort;
交换类排序主要有冒泡排序(bubble sort); 快速排序(quick sort);
选择类排序主要有;简单选择排序(simple selection sort); 堆排序(heap sort);
除此之外还有归并排序(merge sort); 基数排序等;
本篇博客是关于快速排序(quick sort)的;
排序直接的数据结构介绍;
所有的排序均以线性表存储;所有的排序算法避免不了交换;交换就要用到临时变量;故将线性表中编号为0的元素不存储任何有效元素;仅仅当做临时变量或者记录的作用来使用;对于有些算法我会给出局部变量做临时变量的算法;若对线性表不是很了解;参见前面关于线性表的博客;
头文件(sort.h);
# ifndef _SORT_
typedef int KeyType;
typedef struct
{
KeyType key;
}DataType;
# endif
头文件(SeqList.h);
typedef struct
{
DataType data[MAXSIZE];
int length;
}SeqList, * PSeqList;
//线性表排序基本准备;
PSeqList Init_SeqList(void);
bool Full_SeqList(PSeqList p);
int Push_SeqList(PSeqList p, KeyType keyValue);
void Traversal_SeqList(PSeqList p);
ostream & operator<<(ostream & os, DataType dataValue);
//基于线性表的排序方法;默认从小到大;
void StraightInsertSort(PSeqList p);
void BinaryInsertSort(PSeqList p);
void ShellInsert(PSeqList p, int gap);
void ShellSort(PSeqList p, int * gaps, int len);
void BubbleSort(PSeqList p);
void SelectSort(PSeqList p);
void HeapAdjust(PSeqList p, int n, int m);
void HeapSort(PSeqList p);
int BinaryOrder(PSeqList p, int low, int high);
void QuickSort(PSeqList p, int low, int high);
实现文件(SeqList.cpp);
# include "SeqList.h"
PSeqList Init_SeqList(void)
{
PSeqList p = (PSeqList)malloc(sizeof(SeqList));
if (NULL != p)
{
p->length = 0;
return p;
}
else
{
cout << "Memory allocate is error! " << endl;
system("pause");
exit(0);
}
}
bool Full_SeqList(PSeqList p)
{
if (p->length >= MAXSIZE)
{
return true;
}
else
{
return false;
}
}
int Push_SeqList(PSeqList p, KeyType keyValue)
{
if (Full_SeqList(p))
{
cout << "SeqList is full! " << endl;
return -1;
}
p->data[p->length].key = keyValue;
p->length++;
return 0;
}
void Traversal_SeqList(PSeqList p)
{
for (int i = 0; i < p->length; i++)
{
cout << p->data[i] << " ";
}
cout << endl;
return;
}
ostream & operator<<(ostream & os, DataType dataValue)
{
cout << dataValue.key;
return os;
}
//基于线性表的排序方法;默认从小到大;
//直接插入排序;
void StraightInsertSort(PSeqList p)
{
int i = 0;
int j = 0;
for (i = 2; i < p->length; i++)
{
//复制到前哨站;
p->data[0] = p->data[i];
j = i - 1;
while (p->data[0].key < p->data[j].key)//必须是大于;不然不是稳定排序;
{
//移动元素;
p->data[j + 1] = p->data[j];
j--;
}
//元素最终移入正确位置;
p->data[j + 1] = p->data[0];
}
return;
}
//折半插入排序;
void BinaryInsertSort(PSeqList p)
{
int i = 0;
int j = 0;
int low = 0;
int mid = 0;
int high = 0;
for (i = 2; i < p->length; i++)
{
//复制到前哨站;
p->data[0] = p->data[i];
//查找插入位置;
low = 1;
high = i - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (p->data[0].key >= p->data[mid].key)//要么是大于等于要么是小于;即是相反;不然不是稳定排序;
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
//移动元素腾出插入位置;这里high + 1为最终插入位置;
for (j = i - 1; j >= high + 1; j--)
{
p->data[j + 1] = p->data[j];
}
//元素最终移入正确位置;
p->data[j + 1] = p->data[0];
}
return;
}
//Shell插入;
void ShellInsert(PSeqList p, int gap)
{
int i = 0;
int j = 0;
for (i = gap + i; i < p->length; i++)
{
if (p->data[i].key < p->data[i - gap].key)
{
p->data[0] = p->data[i];
for (j = i - gap; (j > 0) && (p->data[0].key < p->data[j].key); j = j - gap)
{
p->data[j + gap] = p->data[j];
}
p->data[j + gap] = p->data[0];
}
}
return;
}
//Shell排序;
void ShellSort(PSeqList p, int * gaps, int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
ShellInsert(p, gaps[i]);
}
return;
}
//冒泡排序;
void BubbleSort(PSeqList p)
{
int i = 0;
int j = 0;
for (i = 1; i < p->length - 1; i++)
{
for (j = 1; j < p->length - i; j++)
{
if (p->data[j].key > p->data[j + 1].key)
{
p->data[0] = p->data[j];
p->data[j] = p->data[j + 1];
p->data[j + 1] = p->data[0];
}
}
}
return;
}
//选择排序;
void SelectSort(PSeqList p)
{
int i = 0;
int j = 0;
int t = 0;
for (i = 1; i < p->length - 1; i++)
{
for (j = i + 1, t = i; j < p->length; j++)
{
if (p->data[t].key > p->data[j].key)
{
t = j;
}
}
if (t != i)
{
p->data[0] = p->data[i];
p->data[i] = p->data[t];
p->data[t] = p->data[0];
}
}
}
void HeapAdjust(PSeqList p, int n, int m)
{
int i = n;
int j = 0;
DataType rec = p->data[i];
for (j = 2 * i; j <= m; j = 2 * j)
{
if ((j < m) && (p->data[j].key < p->data[j + 1].key))
{
j = j + 1;
}
if (rec.key > p->data[j].key)
{
break;
}
else
{
p->data[i] = p->data[j];
i = j;
}
}
p->data[i] = rec;
return;
}
void HeapSort(PSeqList p)
{
int i = 0;
for (i = (p->length - 1) / 2; i > 0; i--)
{
HeapAdjust(p, i, p->length - 1);
}
for (i = p->length - 1; i > 1; i--)
{
p->data[0] = p->data[i];
p->data[i] = p->data[1];
p->data[1] = p->data[0];
HeapAdjust(p, 1, i - 1);
}
return;
}
int BinaryOrder(PSeqList p, int low, int high)
{
KeyType keyValue;
p->data[0] = p->data[low];
keyValue = p->data[low].key;
while (low < high)
{
while ((low < high) && (p->data[high].key >= keyValue))
{
high--;
}
p->data[low] = p->data[high];
while ((low < high) && (p->data[low].key <= keyValue))
{
low++;
}
p->data[high] = p->data[low];
}
p->data[low] = p->data[0];
return low;
}
void QuickSort(PSeqList p, int low, int high)
{
int mid = 0;
if (low < high)
{
mid = BinaryOrder(p, low, high);
QuickSort(p, low, mid - 1);
QuickSort(p, mid + 1, high);
}
return;
}
主函数(Main.cpp);
# include "SeqList.h"
int main(int argc, char ** argv)
{
int val = 0;
PSeqList p = Init_SeqList();
for (int i = 0; i <= 10; i++)
{
Push_SeqList(p, 11 - i);
}
cout << "---------------Sort befor---------------" << endl;
Traversal_SeqList(p);
cout << endl << "---------------Sort after---------------" << endl;
//StraightInsertSort(p);
//BinaryInsertSort(p);
//BubbleSort(p);
QuickSort(p, 1, 10);
//SelectSort(p);
/HeapSort(p);
//MergeSort(p->data, p->data, 1, p->length - 1);
//StraightInsertAllSort(p);
//BinaryInsertAllSort(p);
Traversal_SeqList(p);
system("pause");
return 0;
}
上面的算法只是对{ 1..........N}的元素进行排序;下面给出对{ 0.......N}的元素进行排序的算法;
分析;前面没有排序0号元素是因为0号元素被当做临时变量使用了,现在自定义一个临时变量代替它就可以了;
int BinaryQuickAllSort(PSeqList p, int low, int high)
{
DataType tem = p->data[low];
KeyType midKeyValue = p->data[low].key;
while (low < high)
{
while (low < high && p->data[high].key >= midKeyValue)
{
high--;
}
p->data[low] = p->data[high];
while (low < high && p->data[low].key <= midKeyValue)
{
low++;
}
p->data[high] = p->data[low];
}
p->data[low] = tem;
return low;
}
void QuickAllSort(PSeqList p, int low, int high)
{
int mid = 0;
if (low < high)
{
mid = BinaryQuickAllSort(p, low, high);
QuickAllSort(p, low, mid - 1);
QuickAllSort(p, mid + 1, high);
}
return;
}