• Merge Sort Array: 看完stanford的 CS106B的video，https://www.youtube.com/watch?v=LlNawf0JeF0&list=PLnfg8b9vdpLn9exZweTJx44CII1bYczuk&index=55醍醐灌顶； public class Solution { /** * @param ...
Merge Sort Array: 看完stanford的 CS106B的video，https://www.youtube.com/watch?v=LlNawf0JeF0&list=PLnfg8b9vdpLn9exZweTJx44CII1bYczuk&index=55 醍醐灌顶；

public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
// merge sort;
if(A == null || A.length == 0) return;
int[] temp = new int[A.length];
mergeSort(A, 0, A.length-1, temp);
}

private void mergeSort(int[] A, int start, int end, int[] temp) {
if(start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(A, start, mid, temp);
mergeSort(A, mid+1, end, temp);
merge(A, start, end, temp);
}

private void merge(int[] A, int start, int end, int[] temp) {
int mid = start + (end - start) / 2;
int astart = start;
int bstart = mid+1;

int index = astart; // NOTE: index is astart;
while(astart <= mid && bstart <= end) {
if(A[astart] < A[bstart]) {
temp[index++] = A[astart++];
} else { // A[bstart] < A[astart];
temp[index++] = A[bstart++];
}
}

while(astart <= mid) {
temp[index++] = A[astart++];
}

while(bstart <= end) {
temp[index++] = A[bstart++];
}

// give temp to A;
for(int i=start; i<=end; i++){
A[i] = temp[i];
}

}
}

Merge Sort LinkedList:

Sort a linked list in O(n log n) time using constant space complexity.

思路：merge sort 是nlogn

注意：

1. 分开两个list，找中点的时候，一般是找中点的前一个点，因为前面的list最后一个需要变成null，跟后面分开。

2. merge的时候，为了返回head node必须有个dump，hold住head，然后有个cur作为指针，连接下一个node。

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
private ListNode findMiddle(ListNode node) {
ListNode dummpy = new ListNode(0);
dummpy.next = node;
ListNode slow = dummpy;
ListNode fast = dummpy;

while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

public ListNode sortList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode slow = findMiddle(head);
ListNode newhead = slow.next;
slow.next = null;

ListNode l1 = sortList(head);
ListNode l2 = sortList(newhead);
return MergeTwoSortedList(l1, l2);
}

private ListNode MergeTwoSortedList(ListNode l1, ListNode l2) {
ListNode dummpy = new ListNode(0);
ListNode cur = dummpy;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
} else {
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
}

if(l1 != null) {
cur.next = l1;
}

if(l2 != null) {
cur.next = l2;
}
return dummpy.next;
}
}

3. 这题再联想到：如何用 insertion sort 去sort integer array和 linked list


展开全文
• 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。 归并排序是建立在归并操作上的一种有效的排序算法。...
文章目录算法描述动图演示代码实现算法分析
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现
下面的排序算法统一使用的测试代码如下，源码GitHub链接
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
mergeSort(array);

System.out.println(Arrays.toString(array));
}

/**
* Description: 归并排序
*
* @param array
* @return void
* @author JourWon
* @date 2019/7/11 23:37
*/
public static void mergeSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}

sort(array, 0, array.length - 1);
}

private static void sort(int[] array, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
// 对左侧子序列进行递归排序
sort(array, left, mid);
// 对右侧子序列进行递归排序
sort(array, mid + 1, right);
// 合并
merge(array, left, mid, right);
}

private static void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while (p1 <= mid && p2 <= right) {
temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while (p1 <= mid) {
temp[i++] = array[p1++];
}
while (p2 <= right) {
temp[i++] = array[p2++];
}
// 把最终的排序的结果复制给原数组
for (i = 0; i < temp.length; i++) {
array[left + i] = temp[i];
}
}

算法分析
最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)


展开全文
• code #include <stdio.h> void merge(int a[], int t[], int l, int m, int r...void merge_sort(int a[], int t[], int l, int r); void print_array(int a[], int l, int r); void merge(int a[], int t[]...
code
#include <stdio.h>

void merge(int a[], int t[], int l, int m, int r);
void merge_sort(int a[], int t[], int l, int r);
void print_array(int a[], int l, int r);

void merge(int a[], int t[], int l, int m, int r) {

int l_start = l, r_start = m+1, i = l;

printf("sort before: l=%d, m=%d, r=%d\n", l, m, r);
print_array(a, l, r);

//sort by small values, copy to t[]
while ( l_start <= m && r_start <= r ) {
if (a[l_start] > a[r_start])
t[i++] = a[r_start++];
else
t[i++] = a[l_start++];
}

//handle the remaining left side
while ( l_start <= m ) {
t[i++] = a[l_start++];
}

//handle the remaining right side
while ( r_start <= r ) {
t[i++] = a[r_start++];
}

//copy to origin a[]
for ( i = l; i <= r; i++ ) {
a[i] = t[i];
}

printf("sort after:\n");
print_array(a, l, r);
}

void merge_sort(int a[], int t[], int l, int r) {
if (l < r) {

int m = (r+l)/2;
printf("sort before: l=%d, m=%d, r=%d\n", l, m, r);
merge_sort(a, t, l, m);
merge_sort(a, t, m+1, r);
merge(a, t, l, m, r);
}
}

void print_array(int a[], int l, int r) {
for ( int i = l; i <= r; i++ ) {
printf("%d\t", a[i]);
}

printf("\n");
}

int main () {
int a[9] = {100, 50, 10, 20, 40, 30, 60, 70, 80};

int i, t[9];

merge_sort(a, t, 0, 8);
printf("final printing:\n");
print_array(a, 0, 8);

return 0;
}


result
sort before: l=0, m=4, r=8
sort before: l=0, m=2, r=4
sort before: l=0, m=1, r=2
sort before: l=0, m=0, r=1
sort before: l=0, m=0, r=1
100	50
sort after:
50	100
sort before: l=0, m=1, r=2
50	100	10
sort after:
10	50	100
sort before: l=3, m=3, r=4
sort before: l=3, m=3, r=4
20	40
sort after:
20	40
sort before: l=0, m=2, r=4
10	50	100	20	40
sort after:
10	20	40	50	100
sort before: l=5, m=6, r=8
sort before: l=5, m=5, r=6
sort before: l=5, m=5, r=6
30	60
sort after:
30	60
sort before: l=7, m=7, r=8
sort before: l=7, m=7, r=8
70	80
sort after:
70	80
sort before: l=5, m=6, r=8
30	60	70	80
sort after:
30	60	70	80
sort before: l=0, m=4, r=8
10	20	40	50	100	30	60	70	80
sort after:
10	20	30	40	50	60	70	80	100
final printing:
10	20	30	40	50	60	70	80	100

改进版，无需用额外空间的归并排序
#include <stdio.h>

void merge(int *a, int ll, int lr, int rl, int rr) {
int i = ll, j = rl, swap;
printf("ll=%d, lr=%d, rl=%d, rr=%d\n", ll, lr, rl, rr);
while ( i <= lr) {
printf("swap before: a[%d]=%d, a[%d]=%d\n", rl, a[rl], i, a[i]);
if ( a[rl] < a[i] ) { //比较合并左右最小的元素
swap = a[rl];
a[rl] = a[i];
a[i] = swap;
}
i++;
printf("swap after: a[%d]=%d, a[%d]=%d\n", lr, a[lr], i, a[i]);
j = rl+1;
while (j <= rr && a[j] < a[j-1]) { //整理交换后的右侧数据，使其保持递增
swap = a[j];
a[j] = a[j-1];
a[j-1] = swap;
j++;
}
}
}

void mergeSort(int *a, int l , int r) {
if (l < r) {
int mid = (l + r) >> 1;
printf("l=%d, mid=%d, r=%d\n", l, mid, r);
mergeSort(a, l, mid);
mergeSort(a, mid+1, r);
// printf("ll=%d, lr=%d, rl=%d, rr=%d\n", l, mid, mid+1, r);
merge(a, l, mid, mid+1, r);
}
}

int main() {
int a[7] = {1, 4, 2, 5, 6, 0, 9};

mergeSort(a, 0, 6);

for (int i = 0; i < 7; i++) {
printf("%d ", a[i]);
}
printf("\n");
}

执行过程及结果
l=0, mid=3, r=6
l=0, mid=1, r=3
l=0, mid=0, r=1
ll=0, lr=0, rl=1, rr=1
swap before: a[1]=4, a[0]=1
swap after: a[0]=1, a[1]=4
l=2, mid=2, r=3
ll=2, lr=2, rl=3, rr=3
swap before: a[3]=5, a[2]=2
swap after: a[2]=2, a[3]=5
ll=0, lr=1, rl=2, rr=3
swap before: a[2]=2, a[0]=1
swap after: a[1]=4, a[1]=4
swap before: a[2]=2, a[1]=4
swap after: a[1]=2, a[2]=4
l=4, mid=5, r=6
l=4, mid=4, r=5
ll=4, lr=4, rl=5, rr=5
swap before: a[5]=0, a[4]=6
swap after: a[4]=0, a[5]=6
ll=4, lr=5, rl=6, rr=6
swap before: a[6]=9, a[4]=0
swap after: a[5]=6, a[5]=6
swap before: a[6]=9, a[5]=6
swap after: a[5]=6, a[6]=9
ll=0, lr=3, rl=4, rr=6
swap before: a[4]=0, a[0]=1
swap after: a[3]=5, a[1]=2
swap before: a[4]=1, a[1]=2
swap after: a[3]=5, a[2]=4
swap before: a[4]=2, a[2]=4
swap after: a[3]=5, a[3]=5
swap before: a[4]=4, a[3]=5
swap after: a[3]=4, a[4]=5
0 1 2 4 5 6 9



展开全文
• 递归
Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array a with indices from [l, r) can be implemented as follows:

If the segment [l, r) is already sorted in non-descending order (that is, for any i such that l ≤ i < r - 1 a[i] ≤ a[i + 1]), then end the function call;
Let ;
Call mergesort(a, l, mid);
Call mergesort(a, mid, r);
Merge segments [l, mid) and [mid, r), making the segment [l, r) sorted in non-descending order. The merge algorithm doesn't call any other functions.
The array in this problem is 0-indexed, so to sort the whole array, you need to call mergesort(a, 0, n).

The number of calls of function mergesort is very important, so Ivan has decided to calculate it while sorting the array. For example, if a = {1, 2, 3, 4}, then there will be 1 call of mergesort — mergesort(0, 4), which will check that the array is sorted and then end. If a = {2, 1, 3}, then the number of calls is 3: first of all, you call mergesort(0, 3), which then sets mid = 1 and calls mergesort(0, 1) and mergesort(1, 3), which do not perform any recursive calls because segments (0, 1) and (1, 3) are sorted.

Ivan has implemented the program that counts the number of mergesort calls, but now he needs to test it. To do this, he needs to find an array a such that a is a permutation of size n (that is, the number of elements in a is n, and every integer number from [1, n] can be found in this array), and the number of mergesort calls when sorting the array is exactly k.

Help Ivan to find an array he wants!

Input

The first line contains two numbers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 200000) — the size of a desired permutation and the number of mergesort calls required to sort it.

Output

If a permutation of size n such that there will be exactly k calls of mergesort while sorting it doesn't exist, output  - 1. Otherwise output n integer numbers a[0], a[1], ..., a[n - 1] — the elements of a permutation that would meet the required conditions. If there are multiple answers, print any of them.

Examples

Input

Copy

3 3

Output

Copy

2 1 3

Input

Copy

4 1

Output

Copy

1 2 3 4

Input

Copy

5 6

Output

Copy

-1

考虑模拟该归并排序的过程。

第一次调用merge_sort（0,n），之后不管怎样哪一部分有序无序的，调用都是成对出现的，故初始的k必须为奇数，若为偶数，一定不可行。

设计dfs函数是一个难点。不能确定每一部分究竟是有序还是无序。

那么我们开始时默认已排好序，如果当前调用次数cnt还不足k的话，就把当前序列搞成无序（但两部分均有序），继续向下递归。

把当前有序序列搞成整体无序但两部分均有序的方法：①把中点m两旁的元素换一下就好了②左右两边整体调换一下也行

最后cnt==k或者区间已经不能再分时返回。

#include<bits/stdc++.h>
using namespace std;

int n,k,a[100000+1000],cnt;

void dfs(int l,int r)   //  [  ,  )
{
if(r-l==1||cnt==k)return;
int m=(l+r)/2;
swap(a[m-1],a[m]);
cnt+=2;
dfs(l,m);
dfs(m,r);
}

int main()
{
//	freopen("input.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)a[i]=i+1;
cnt++;
if(!(k&1))cout<<-1<<endl;
else
{
dfs(0,n);
if(cnt<k)cout<<-1<<endl;
else for(int i=0;i<n;i++)cout<<a[i]<<" ";
}
return 0;
}


展开全文
• //算法导论笔记 分冶（？）法排序 核心思想：  -设Llist与Rlist已经被排好序；//MERGE  将其合并时：分别考察二者头部，选取符合... //MERGE_SORT  递归地——base case为SubList仅有一个元素，其余情况Sub
• pseudocode：MERGE-SORTA[1 . . n] 1.If n= 1, done. 2.Recursively sort A[ 1 . . ⎡n/2⎤]and A[ ⎡n/2⎤+1 . . n ] . 3.“Merge”the 2sorted lists.C++: const int N = 100; void merge(int * a,int lhs,int mid...

...