sort list

# 尝试快排

```int partitionB(int *a, int left, int right) {
int x = left, y = right, t = a[right];
while (x < y) {
while (x < y && a[x] <= t) ++x;
a[y] = a[x];
while (x < y && a[y] > t) --y;
a[x] = a[y];
}
a[y] = t;
return x;
}```

```int partitionA(int *a, int left, int right) {
int x = left-1, y = left;
for (; y < right; ++y) {
if (a[y] < a[right]) {
int tmp = a[y];
a[y] = a[++x];
a[x] = tmp;
}
}
int tmp = a[x+1];
a[x+1] = a[right];
a[right] = tmp;
return x+1;
}```

#### 方法二的思考

```class Solution {
private:
void exchangeNodes(ListNode *xPre, ListNode *yPre) {
if (!xPre || !yPre) return;
ListNode *x = xPre->next, *y = yPre->next;
if (!x || !y || x == y) return;
if (x->next == y) {
ListNode *ySuf = y->next;
xPre->next = y;
y->next = x;
x->next = ySuf;
} else if (y->next == x) {
ListNode *xSuf = x->next;
yPre->next = x;
x->next = y;
y->next = xSuf;
} else {
ListNode *xSuf = x->next, *ySuf = y->next;
xPre->next = y;
yPre->next = x;
y->next = xSuf;
x->next = ySuf;
}
}
ListNode *partition(ListNode *head, ListNode *start, ListNode **end) {
ListNode *x = start, *y = start->next, *yPre = start;
while (y && y != *end) {
if (y->val < (*end)->val) {
exchangeNodes(x, yPre);
x = x->next;
}
yPre = y;
y = y->next;
}
exchangeNodes(x, yPre);
*end = yPre->next;
return x;
}
void quikSort(ListNode *head, ListNode *start, ListNode *end) {
if (!start || !end || start == end || start->next == end) return;
ListNode *tmp = partition(head, start, &end);
}
public:
ListNode *root = (ListNode *)malloc(sizeof(ListNode));
while (foot->next) foot = foot->next;
quikSort(root, root, foot);
return root->next;
}
};```

# 尝试归并

```void mergeSort(int *a, int left, int right) {
if (left + 1 >= right) return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid, right);
mergeA(a, left, mid, right);
}```

```void mergeA(int *a, int left, int mid, int right) {
int n0 = mid - left, n1 = right - mid;
int tmpA[n0], tmpB[n1];
for (int i = 0; i < n0; ++i) tmpA[i] = a[i + left];
for (int i = 0; i < n1; ++i) tmpB[i] = a[i + mid];
int x = 0, y = 0;
for (int i = left; i <= right; ++i) {
if (x >= n0 && y >= n0) break;
if (y >= n1 || (x < n0 && tmpA[x] <= tmpB[y])) a[i] = tmpA[x++];
else a[i] = tmpB[y++];
}
}```

```class Solution {
private:
void insertNode(ListNode **leftPre, ListNode *rightPre) {
ListNode *target = rightPre->next;
rightPre->next = target->next;
ListNode *sureSuf = (*leftPre)->next;
(*leftPre)->next = target;
target->next = sureSuf;
*leftPre = target;
}
ListNode* merge(ListNode *start, ListNode *mid, ListNode *end) {
ListNode *xPre = start, *yPre = mid, *end_next = end->next;
while (xPre != mid || yPre->next != end_next) {
if (xPre == mid) {
yPre = yPre->next;
} else if (yPre->next == end_next) {
xPre = xPre->next;
} else {
if (xPre->next->val <= yPre->next->val) {
xPre = xPre->next;
} else {
insertNode(&xPre, yPre);
}
}
}
return yPre;
}
ListNode* mergeSort(ListNode *start, ListNode *end) {
if (!start || !start->next || start->next == end) return end;
ListNode *low = start->next, *fast = start->next;
while (fast && fast->next && fast->next != end->next && fast->next->next && fast->next->next != end->next) {
low = low->next;
fast = fast->next->next;
}
ListNode *tmp_low = mergeSort(start, low);
ListNode *tmp_end = mergeSort(tmp_low, end);
return merge(start, tmp_low, tmp_end);
}
public:
ListNode *root = (ListNode *)malloc(sizeof(ListNode));
while (foot->next) foot = foot->next;
mergeSort(root, foot);
return root->next;
}
};```

# 写在后面

38 篇文章26 人订阅

0 条评论

## 相关文章

### java基础学习_面向对象(上)01_day07总结

============================================================================= ==...

10220

### 用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程（FP）《Kotlin极简教程》正式上架：

"函数式编程", 又称泛函编程, 是一种"编程范式"（programming paradigm），也就是如何编写程序的方法论。它的基础是 λ 演算（lambda...

17140

19130

### 3. call PRXSUBSTR () | 庖丁解牛切割数据！

【SAS Says·扩展篇】庖丁解牛割数据！ | 3. call PRXSUBSTR () 0. 前集回顾 1. 新的问题 2. 初识 PRXSUBSTR() ...

36050

13220

### Java Map中常遇到的几个问题

1.将Map转化成List Map接口提供了三种collection：key set,value set 和 key-value set，每一种都可以转成Lis...

30340

29270

### Sweet Snippet 之 Bounce Setting

又是一篇Sweet Snippet，自己看来都觉得过小，不足以成篇，不过自觉有些趣味，也就随便记一记了，权当自娱自乐 ：）

6710

28080

33660