java nodelist 快速排序_数据结构的实践心得（归并排序和快速排序：mergeSort、quickSort）...
数据结构的实践心得(归并排序和快速排序：mergeSort、quickSort)
COMZHJ 咕咚的小宇宙
归并排序和快速排序(mergeSort、quickSort)：
// 归并排序
void mergeSort(linkQueue *que);
// 快速排序
void quickSort(linkQueue *que);
// 合并两个有序序列
int merge(doubleNode **mergeList, int start, int mid, int end)
{
int count = 0;
// 创建临时内存空间存储合并后结果
doubleNode **list = (doubleNode **)malloc(sizeof(doubleNode *) * (end - start + 1));
int left = start, right = mid + 1, index = 0;
// 两个有序序列中元素的比较合并
while ((left <= mid) || (right <= end))
{
count++;
// 逐个比较两个序列节点的优先级
if (left > mid)
{
list[index++] = mergeList[right++];
}
else if (right > end)
{
list[index++] = mergeList[left++];
}
else if (mergeList[left]->data[PriorityINDEX] > mergeList[right]->data[PriorityINDEX])
{
list[index++] = mergeList[right++];
}
else
{
list[index++] = mergeList[left++];
}
}
int i;
// 将合并结果写回原来的数组
for (i = 0; i < index; i++)
{
count++;
mergeList[start + i] = list[i];
}
// 释放临时内存空间
free(list);
return count;
}
// 归并排序(指针数组)
int mergePointArray(doubleNode **mergeList, int start, int end)
{
int count = 0;
// 只有一个元素，视作有序，结束分割
if (end <= start) return count;
// 取得中间数
int mid = (end + start) / 2;
// 递归分割第一个序列
count += mergePointArray(mergeList, start, mid);
// 递归分割第二个序列
count += mergePointArray(mergeList, mid + 1, end);
// 合并两个有序序列
count += merge(mergeList, start, mid, end);
return count;
}
// 归并排序
void mergeSort(linkQueue *que)
{
// 取得优先队列的链表数据长度
int len = que->doubleLink.len;
if (len <= 1) return;
doubleNode **mergeList = (doubleNode **)malloc(sizeof(doubleNode *) * len);
// 定义一个指针，首先指向头节点
doubleNode *p = que->doubleLink.head;
int asdf = 0;
int i;
// 把优先队列的数据，装入指针数组
for (i = 0; i < len; i++)
{
asdf++;
mergeList[i] = p;
p = p->next;
}
// 归并排序(指针数组)
asdf += mergePointArray(mergeList, 0, len - 1);
// 首先指向尾节点
p = mergeList[len - 1];
// 把优先队列的数据，装入指针数组
for (i = 0; i < len; i++)
{
asdf++;
// 更新前后节点关系
p->next = mergeList[i];
mergeList[i]->prev = p;
p = mergeList[i];
}
printf("归并排序算法复杂度=%d\n", asdf);
// 更新头节点
que->doubleLink.head = mergeList[0];
// 释放指针数组的内存空间
free(mergeList);
// 更新队前和队尾节点
que->front = que->doubleLink.head;
que->rear = que->doubleLink.head->prev;
}
// 快速排序(指针数组)
int quickPointArray(doubleNode **mergeList, int start, int end)
{
int count = 0;
// 序列中没有元素或只有一个元素，递归结束
if (end <= start) return count;
int left = start, right = end, hole = start;
doubleNode *temp = mergeList[start];
while (left < right)
{
count++;
// 从right位置开始从后往前找第一个小于temp的值
while ((left < right) && (temp->data[PriorityINDEX] <= mergeList[right]->data[PriorityINDEX]))
{
right--;
}
if (left == right) break;
mergeList[hole] = mergeList[right];
hole = right;
count++;
// 从left位置开始从前往后找第一个大于temp的值
while ((left < right) && (temp->data[PriorityINDEX] >= mergeList[left]->data[PriorityINDEX]))
{
left++;
}
if (left == right) break;
mergeList[hole] = mergeList[left];
hole = left;
}
mergeList[hole] = temp;
// 对标杆位置左边的序列实施同样的方法
count += quickPointArray(mergeList, start, hole - 1);
// 对标杆位置右边的序列实施同样的方法
count += quickPointArray(mergeList, hole + 1, end);
return count;
}
// 快速排序
void quickSort(linkQueue *que)
{
// 取得优先队列的链表数据长度
int len = que->doubleLink.len;
if (len <= 1) return;
doubleNode **mergeList = (doubleNode **)malloc(sizeof(doubleNode *) * len);
// 定义一个指针，首先指向头节点
doubleNode *p = que->doubleLink.head;
int asdf = 0;
int i;
// 把优先队列的数据，装入指针数组
for (i = 0; i < len; i++)
{
asdf++;
mergeList[i] = p;
p = p->next;
}
// 进行快速排序
asdf += quickPointArray(mergeList, 0, len - 1);
// 首先指向尾节点
p = mergeList[len - 1];
// 把优先队列的数据，装入指针数组
for (i = 0; i < len; i++)
{
asdf++;
p->next = mergeList[i];
mergeList[i]->prev = p;
p = mergeList[i];
}
printf("快速排序算法复杂度=%d\n", asdf);
// 更新头节点
que->doubleLink.head = mergeList[0];
// 释放指针数组的内存空间
free(mergeList);
// 更新队前和队尾节点
que->front = que->doubleLink.head;
que->rear = que->doubleLink.head->prev;
}