分类： IT业界
2011-06-09 15:20:16
1、数据结构 （以下的算法中直接插入，快排使用的该数据结构，其余的都选用的整形数组）
#define MAXNUM 100
struct Record
{
int key;
char Info[100];
};
struct SqList
{
struct Record r[MAXNUM];
int length;
};
1、 直接插入排序
void InsertSort(struct SqList &L)
{
for (int i = 2; i <= L.length; i++)
{
if (L.r[i].key <= L.r[i-1].key)
{
L.r[0] = L.r[i];
L.r[i] = L.r[i-1];
for (int j = i - 2; L.r[0].key <= L.r[j].key; j--)
{
L.r[j+1] = L.r[j];
}
L.r[j+1] = L.r[0];
}
}
}
2、 快速排序
int Parttion(struct SqList &L, int low, int high)
{
L.r[0] = L.r[low];
int pivotloc = L.r[low].key;
while (low < high)
{
while (low < high && L.r[high].key >= pivotloc) //找到一个关键字小于pivotloc的记录
{
high--;
}
L.r[low] = L.r[high];
while (low < high && L.r[low].key <= pivotloc) //找到一个关键字大于pivotloc的记录
{
low++;
}
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void QSort(struct SqList &L, int low, int high)
{
if (low < high)
{
int pivotloc = Parttion(L, low, high);
QSort(L, low, pivotloc -1);
QSort(L, pivotloc + 1, high);
}
}
void QuickSort(struct SqList &L)
{
QSort(L, 1, L.length);
}
3、 冒泡排序
void BubbleSort(int array[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i ; j++)
{
if (array[j] > array[j+1])
{
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
}
}
}
}
4、 选择排序
void SelectSort(int array[], int len)
{
int i, j, k;
for (i = 0; i < len -1; i++)
{
k = i;
for (j=i+1; j < len; j++)
{
if (array[j] < array[k])
{
k = j;
}
}
int tmp = array[k];
array[k] = array[i];
array[i] = tmp;
}
}
5、 堆排序
void AdjustHeap(int array[], int s, int m)
{
//实现一：此种方法可以减少赋值的次数
//int rc = array[s];
//for (int j = 2*s; j <= m; j *= 2)
//{
// if (j < m && array[j] < array[j+1])
// {
// j++;
// }
// if (rc >= array[j])
// {
// break;
// }
// array[s] = array[j];
// s = j;
//}
//array[s] = rc;
//实现二：此种方法增加了赋值的次数
for (int j = 2*s; j <= m; j *= 2)
{
if (j < m && array[j] < array[j+1])
{
j++;
}
if (array[s] >= array[j])
{
break;
}
int tmp;
tmp = array[s];
array[s] = array[j];
array[j] = tmp;
s = j;
}
}
void HeapSort(int array[], int len)
{
for (int i = len/2; i >= 0; i--)
AdjustHeap(array, i, len - 1);
for (i = len -1; i >= 0; i --)
{
int tmp;
tmp = array[0];
array[0] = array[i];
array[i] = tmp;
AdjustHeap(array, 0, i - 1);
}
}
6、 归并排序
方法一：
void Merge(int array[], int start, int mid, int end)
{
int nLeft = mid - start+1;
int nRight = end - mid;
int *LeftArray = new int [nLeft];
int *RightArray = new int [nRight];
for (int i = 0; i < nLeft; i++)
{
LeftArray[i] = array[start + i];
}
for (int j = 0; j < nRight; j++)
{
RightArray[j] = array[j+mid+1];
}
int k;
i = 0;
j = 0;
for (k = start; k <= end && i < nLeft && j < nRight; k++)
{
if (LeftArray[i] < RightArray[j])
{
array[k] = LeftArray[i++];
}
else
{
array[k] = RightArray[j++];
}
}
while (i < nLeft)
{
array[k++] = LeftArray[i++];
}
while (j < nRight)
{
array[k++] = RightArray[j++];
}
delete []LeftArray;
delete []RightArray;
}
void MergeSort(int array[], int start, int end)
{
if (end > start)
{
int mid = (start + end) / 2;
MergeSort(array, start, mid);
MergeSort(array, mid+1, end);
Merge(array, start, mid, end);
}
}
方法二：
void Merge(int SR[], int TR[], int i, int m, int n)
{
for (int j = m+1, k = i; i <= m && j <= n; k++)
{
if (SR[i] < SR[j])
{
TR[k] = SR[i++];
}
else
{
TR[k] = SR[j++];
}
}
while (i <= m)
{
TR[k++] = SR[i++];
}
while (j <= n)
{
TR[k++] = SR[j++];
}
}
void MSort(int SR[], int TR[], int s, int t)
{
if (s == t)
{
TR[s] = SR[s];
}
else
{
int m = (s+t)/2;
int TR2[20]; //这个地方的数组大小应该为t-s+1，但是在具体实现
//时没有找到合适的方法动态申请空间
MSort(SR, TR2, s, m);
MSort(SR, TR2, m+1, t);
Merge(TR2, TR, s, m, t);
}
}
void MergeSort(int SR[], int len)
{
MSort(SR, SR, 0, len-1);
}
