这两个排序算法放在一起的原因是因为他们的执行效率都很高，并且更重要的是他们的实现思路都是利用分治法进行实现的。分治法的意思大致就是把复杂问题细分成很多个简单的问题，逐个解决简单的问题，再将每个小问题的结果合并，这样大的复杂的问题也就得到了解决
快速排序
Java实现
/***
* 3 9 4 2 8 7 1 5 6
* 思路：取数组第一个数为基准，在数组的头和尾设置两个指针。
* 开始遍历，先比较尾指针的值和基准数的大小，如果大，则尾指针前移一位。
* 否则，把尾指针的值放到头指针位置，头指针后移一位。尾指针停止，头指针开始移动。
* 还是和基准数比较大小，如果小，则头指针后移一位。否则，将当前值放置到尾指针处，尾指针前移一位，尾指针开始移动。
* 反复执行此操作，直到头尾指针相遇，将基准数放置在指针的相遇处。此时基准数的左边都是小于它的数字，右边都是大于它的数。
* 再分别将它的左边和右边当成一个独立的数组执行上面的操作。细分的数组长度就每次以一半的速度递减。直到数组排序完成
* 时间复杂度：O(nlogn)
* 3 1 9 4 2 8 7 3 5 6
* 1 3 4 2 8 7 9 5 6
* 1 2 4 3 8 7 9 5 6
* 1 2 3 4 8 7 9 5 6
*/
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if ((rightIndex - leftIndex) < 1) return;
int left = leftIndex;
int right = rightIndex;
// 设置数组中第一个数字为基准数，因为基准数是数组的最左边，所以从最右边向最左边开始遍历
boolean directionLeft = true;
int flag = arr[leftIndex];
while (leftIndex != rightIndex) {
if (directionLeft) {
// right to left
if (arr[rightIndex] > flag) {
rightIndex--;
} else {
arr[leftIndex++] = arr[rightIndex];
directionLeft = !directionLeft;
}
} else {
// left to right
if (arr[leftIndex] < flag) {
leftIndex++;
} else {
arr[rightIndex--] = arr[leftIndex];
directionLeft = !directionLeft;
}
}
}
arr[leftIndex] = flag;
quickSort(arr, left, leftIndex - 1);
quickSort(arr, leftIndex + 1, right);
}
C实现
void quickSort(int *arr, int left, int right){
if ((right - left) < 1)
{
return;
}
int flag = arr[left];
int pLeft = left;
int pRight = right;
// orientation为1：从右向左 为0：从左向右
int orientation = 1;
while (pLeft < pRight)
{
if (orientation)
{
if (arr[pRight] > flag)
{
pRight--;
}
else
{
arr[pLeft++] = arr[pRight];
orientation = 0;
}
}
else
{
if (arr[pLeft] < flag)
{
pLeft++;
}
else
{
arr[pRight--] = arr[pLeft];
orientation = 1;
}
}
}
arr[pLeft] = flag;
quickSort(arr, left, pLeft - 1);
quickSort(arr, pLeft + 1, right);
}
快速排序速度虽然快，但是存在一些使用上的限制，如果待排序的数组结构不是顺序结构，也就是数组结构。而是单链表结构的数据，那么指针的前移将是它的致命缺点，此时就需要归并排序来解决此问题
Java实现
此方法是将一个数组中的left到right进行排序，但是此数组需要一些特殊条件，就是left到mid和mid到right一定是两个有序的小数组。将left-mid和mid-right生成两个新的小数组。每个小数组维护一个指针指向数组头部，比较两个指针所指向的值。哪个值小，就从原数组的left处开始放置。指针后移，直到其中一个数组没有数据了。如果另一个小数组中还有剩余数据，将剩余数据继续放置到原数组中。执行完此方法，数组中从left到right处的数据就完成了排序
/**
* 1 2 3 5 7 2 4 6 8
*/
private static void merge(int[] arr, int left, int mid, int right) {
int[] leftArr = new int[mid - left];
int[] rightArr = new int[right - mid + 1];
for (int i = left; i < mid; i++) {
leftArr[i - left] = arr[i];
}
for (int i = mid; i < right + 1; i++) {
rightArr[i - mid] = arr[i];
}
int pLeft = 0;
int pRight = 0;
int pArr = left;
while (pLeft < leftArr.length && pRight < rightArr.length) {
if (leftArr[pLeft] <= rightArr[pRight]) {
arr[pArr++] = leftArr[pLeft++];
} else {
arr[pArr++] = rightArr[pRight++];
}
}
if (pLeft < leftArr.length) {
for (int i = pLeft; i < leftArr.length; i++) {
arr[pArr++] = leftArr[i];
}
}
if (pRight < rightArr.length) {
for (int i = pRight; i < rightArr.length; i++) {
arr[pArr++] = rightArr[i];
}
}
}
递归调用将数组细分成很多小数组，按位置排序合并后再让较大的数组合并排序
private static void mergeSort(int arr[], int left, int right) {
if (right == left) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid + 1, right);
}
C 实现 (单链表数据结构)
typedef struct NODE
{
NODE *next;
int data;
}Node;
/*
创建链表:随机生成10个数据
*/
void createList(Node *head){
Node *pNode = head;
for (int i = 0; i < 10; i++)
{
Node *node = (Node *)malloc(sizeof(Node));
node->data = rand()%10+1;
node->next = NULL;
pNode->next = node;
pNode = node;
}
}
/*
遍历链表
*/
void printList(Node *head){
Node *pNode = head;
while (pNode->next != NULL)
{
pNode = pNode->next;
printf("%d\t",pNode->data);
}
}
/*
将链表从mid分为两个有序子链表，再把两个有序子链表排序放回原链表中
*/
void merge(Node *head,int left,int mid,int right){
// 创建两个新的链表
Node *leftHead = (Node *)malloc(sizeof(Node));
Node *rightHead = (Node *)malloc(sizeof(Node));
Node *leftControlNode = leftHead;
Node *rightControlNode = rightHead;
Node *pNode = head;
// 移动指针到原链表的left处
for (int i = 0; i < left; i++)
{
pNode = pNode->next;
}
// 从原链表的left处开始遍历原链表，将left和Mid之间node加入到left链表中。将right和mid之间的node加入到right链表中
for (int i = left; pNode->next != NULL && i < right + 1; i++)
{
pNode = pNode->next;
if (i < mid)
{
Node *node = (Node *)malloc(sizeof(Node));
node->data = pNode->data;
node->next = NULL;
leftControlNode->next = node;
leftControlNode = node;
}
else{
Node *node = (Node *)malloc(sizeof(Node));
node->data = pNode->data;
node->next = NULL;
rightControlNode->next = node;
rightControlNode = node;
}
}
// 将两个左右链表排序并合并：设置两个指针分别指向链表第一个node，比较值，较小的加入大链表的left处，指针后移
// 直到某一个遍历完毕，将另一个链表剩余的node依次加入到大链表中，完成排序
Node *pLeft = leftHead->next;
Node *pRight = rightHead->next;
Node *pNodeHead = head;
// 移动指针到大链表的left处
for (int i = 0; i < left; i++)
{
pNodeHead = pNodeHead->next;
}
while (pLeft != NULL && pRight != NULL)
{
if (pLeft->data <= pRight->data)
{
pNodeHead->next = pLeft;
pNodeHead = pLeft;
pLeft = pLeft->next;
}
else{
pNodeHead->next = pRight;
pNodeHead = pRight;
pRight = pRight->next;
}
}
// left链表中还有剩余node，加入到大链表中
while (pLeft != NULL)
{
pNodeHead->next = pLeft;
pNodeHead = pLeft;
pLeft = pLeft->next;
}
// right链表中还有剩余node，加入到大链表中
while (pRight != NULL)
{
pNodeHead->next = pRight;
pNodeHead = pRight;
pRight = pRight->next;
}
// 将原链表right之后的节点添加到新生成的链表中
pNode = pNode->next;
while (pNode != NULL)
{
pNodeHead->next = pNode;
pNodeHead = pNode;
pNode = pNode->next;
}
}
// 排序
void mergeSort(Node *head,int left,int right){
if ((right - left) < 1)
{
return;
}
int mid = (left + right) / 2;
mergeSort(head,left,mid);
mergeSort(head,mid+1,right);
merge(head,left,mid+1,right);
}
网友评论