快速排序进阶

三月不练手生。翻出了以前写的快速排序、单链表快排和scala快排。老老实实写把基础版写对就足够。 本文代码均经过测试。

1，快速排序的C++写法：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int getPartition(int arr[], int low, int high) { int key = arr[low]; while(low < high) { while(low < high && key <= arr[high]) --high; std::swap(arr[low], arr[high]); while(low < high && key >= arr[low]) ++low; std::swap(arr[low], arr[high]); } return low; } void quickSort(int buf[], int low, int high) { if(low < high) { int key = getPartition(buf, low, high); quickSort(buf, low, key-1); quickSort(buf, key+1, high); } }

这是一个常规写法。如果是C单链表，不能随机访问数组array[index]，怎么快排？

2，单链表快排 如下：

//单链表快速排序 typedef struct link_node { int data; struct link_node* next; }Node; void swap(Node* a, Node*b) { if(a->data == b->data) return; int t = a->data; a->data = b->data; b->data = t; } Node* getPart(Node* begin, Node* end) { if(!begin) return NULL; int data = begin->data; Node* p = begin; Node* q = p->next; while(q != end) { if(q->data < data) { p = p->next; swap(p, q); } q = q->next; } swap(p, begin); return p; } void QuickSort(Node* begin, Node* end) { if(begin != end) { Node* partition = getPart(begin, end); QuickSort(begin, partition); QuickSort(partition->next, end); } }

纯C的测试程序如下：

#include <stdio.h> #include <stdlib.h> // 这里include quik_sort()头文件 //insert by head 头插法创建链表。 Node* create_list(int size) { Node* head; head = NULL; while(size--) { Node *t = (Node*)malloc(sizeof(Node)); t->data = rand()%100; t->next = head; head = t; } return head; } void show_list(Node* head) { Node* p=head; while(p) { printf("-", p->data); p = p->next; if(p) printf("->"); } printf("\n"); } void del_list(Node* head) { Node* p = head; while(p) { head = p->next; free(p); p = head; } } int main(int argc, char* argv[]) { Node* link = create_list(10); if(!link) { exit(0); } show_list(link); //Node* p = getPart(link, NULL); //printf("get %d\n", p->data); QuickSort(link, NULL); show_list(link); del_list(link); return 0; }

3，scala实现快排 如下：

// 看起来简洁，测试时并不快。 def quickSort1(sortList:Array[Int]):Array[Int] = { if(sortList.length <= 1) sortList else{ val pivot = sortList(sortList.length / 2) Array.concat( quickSort1(sortList.filter(pivot > _)), sortList.filter(pivot ==), quickSort1(sortList.filter(pivot < _)) ) } } // 正确的写法： def quickSort2(arr: Array[Int]): Array[Int] = { def qsort(left: Int, right: Int) { if (left < right) { var m = left for (i <- left+1 to right) { if (arr(i) < arr(left)) { m += 1 swapArr(arr, i, m) } } swapArr(arr, left, m) qsort(left, m-1) qsort(m+1, right) } } qsort(0, arr.length - 1) arr } def swapArr(arr:Array[Int], a:Int, b:Int) = { val temp = arr(a) arr(a) = arr(b) arr(b) = temp }