1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
| #include <bits/stdc++.h> using namespace std;
void showArray(int *a, int n){ for(int i=0; i<n; i++){ printf("%d ", a[i]); } printf("\n"); }
void quickSort(int *a, int l, int r){ if(l>=r) return;
int pivot = a[l]; int j = l; for(int i=l+1; i<r; i++){ if(a[i] < pivot) swap(a[++j], a[i]); } swap(a[l], a[j]);
quickSort(a, l, j); quickSort(a, j+1, r); }
void quickSort(int *a, int l, int r){ if(l>=r) return;
int pivot = a[l]; int i=l+1, j=r-1; while(i<=j){ while(a[i]<pivot && i<r) i++; while(a[j]>pivot && j>l) j--; if(i>j) break; swap(a[i++], a[j--]); } swap(a[l], a[j]);
quickSort(a, l, j); quickSort(a, j+1, r); }
void quickSort(int *a, int l, int r){ if(l>=r) return;
int pivot = a[l]; int lt = l, rt = r; for(int i=l+1; i<rt; ){ if(a[i] < pivot) swap(a[i++], a[++lt]); else if(a[i] > pivot) swap(a[i], a[--rt]); else i++; } swap(a[l], a[lt]);
quickSort(a, l, lt); quickSort(a, rt, r); }
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };
void showList(ListNode *head){ ListNode *p = head; while(p!=nullptr){ printf("%d ", p->val); p = p->next; } printf("\n"); }
void quickSort(ListNode *head, ListNode *last){ if(head==nullptr || head==last) return;
int pivot = head->val; ListNode *pre = head; for(ListNode *cur=head; cur->next!=last; cur=cur->next){ if(cur->next->val < pivot){ swap(cur->next->val, pre->next->val); pre = pre->next; } } swap(head->val, pre->val);
quickSort(head, pre); quickSort(pre->next, last); }
int main() { int n = 10; int a[11] = {4,1,7,6,9,2,8,0,3,5};
ListNode *h[10]; for(int i=0; i<n; i++){ h[i] = new ListNode(a[i]); if(i) h[i-1]->next = h[i]; } ListNode *head = h[0];
showArray(a, n); quickSort(a, 0, n); showArray(a, n);
showList(head); quickSort(head, nullptr); showList(head);
return 0; }
|