链表排序之快排与归并(递归与非递归)

1.对链表进行快速排序

以【4，2，5，3，7，9，0，1】为例，我们来模拟一趟快排的过程。

**1、**初始化时，i指向链表首元素4；j = i +1，指向2。基准数字为当前i 指向的数字：4。

	j
4	2	5	3	7	9	0	1
i

**2、**随后开始循环，j 当前指向2，因为2小于4，所以要把2移动到前面去。按照我们的算法步骤操作：

• i ++，首先 i 向后移动一位，指向2
• swap(i， j) ，随后交换 i、j 位置的值，这里面是2和2自己交换
• j ++，然后 j 向后移动一位，指向5

执行一次交换后的结果如下：

		j
4	2	5	3	7	9	0	1
	i

**3、**接下来，由于 j 指向的值5 大于4，直接跳过，执行j++，此时 j 指向3

			j
4	2	5	3	7	9	0	1
	i

4、 j 指向的值为3，小于4，仿照步骤2，我们再次执行一次交换移动过程。

• i ++，首先 i 向后移动一位，指向5
• swap(i， j) ，随后交换 i、j 位置的值，这里面是5和3交换
• j ++，然后 j 向后移动一位，指向7

交换后的结果如下：

				j
4	2	3	5	7	9	0	1
		i

5、 j指向的值为7，大于4，所以直接跳过，执行 j++，j 指向9

					j
4	2	3	5	7	9	0	1
		i

**6、**同理，j 指向的值为9，也大于4，跳过，执行 j++，j 指向0

						j
4	2	3	5	7	9	0	1
		i

7、 j 指向的值为0，小于4，执行一次交换过程

• i ++，首先 i 向后移动一位，指向5
• swap(i， j) ，随后交换 i、j 位置的值，这里面是5和0交换
• j ++，然后 j 向后移动一位，指向1

交换后的结果如下：

							j
4	2	3	0	7	9	5	1
			i

8、 j 指向的值为1，小于4，我们再执行一次交换过程

• i ++，首先 i 向后移动一位，指向7
• swap(i， j) ，随后交换 i、j 位置的值，这里面是7和1交换
• j ++，然后 j 向后移动一位，已经超过了链表的长度，不再向后移动。

交换后的结果如下：

								j
4	2	3	0	1	9	5	7
				i

**9、**最后，交换当前 i指向的值1，和4。得到【1、2、3、0、4、9、5、7】，一趟排序结束。

								j
1	2	3	0	4	9	5	7
				i

我们发现，4的左边都是小于4的数字，右边都是大于4的数字。
接下来，对左边和右边分别排序，不断递归下去，直到元素全部有序。

代码如下：

非递归-用栈:

java">package com.m.test;

import java.util.Stack;
import java.util.LinkedList;
import java.util.List;

public class Test {

	public static void fun1(List<Integer> arr, int left, int right) {
		Stack<Integer> stack = new Stack<Integer>();
		if (left < right) {
			stack.add(left);
			stack.add(right);
			while (!stack.isEmpty()) {
				int ri = stack.pop();
				int le = stack.pop();
				int k = quickSort1(arr, le, ri);
				if (le < k - 1) {
					stack.push(le);
					stack.push(k - 1);
				}
				if (ri > k + 1) {
					stack.push(k + 1);
					stack.push(ri);
				}

			}
		}
	}

	public static int quickSort1(List<Integer> list, int left, int right) {
		dealPivot1(list, left, right);
		int pivot = right - 1;
		int i = left;
		int j = pivot;

		while (true) {
			while (list.get(++i) < list.get(pivot)) {
			}
			while (j > left && list.get(--j) > list.get(pivot)) {
			}
			if (i < j) {
				swap1(list, i, j);
			} else {
				break;
			}
		}
		if (i < right) {
			swap1(list, i, right - 1);
		}
		return i;
	}

	public static void dealPivot1(List<Integer> list, int left, int right) {
		int mid = (left + right) / 2;
		if (list.get(left) > list.get(right)) {
			swap1(list, left, right);
		}
		if (list.get(left) > list.get(mid)) {
			swap1(list, left, mid);
		}
		if (list.get(mid) > list.get(right)) {
			swap1(list, mid, right);
		}

		swap1(list, mid, right - 1);
	}

	public static void swap1(List<Integer> list, int a, int b) {
		int t = list.get(a);
		list.set(a, list.get(b));
		list.set(b, t);
	}

	public static void main(String[] args) {
		int[] arr = { 1, 3, -5, 7, -9, -8, -4, -3, -777 };
		long startTime = System.currentTimeMillis();
		LinkedList<Integer> linkedList = new LinkedList<>();
		for (Integer i : arr) {
			linkedList.add(i);
		}
		fun1(linkedList, 0, linkedList.size() - 1);
		System.out.println(linkedList);
		System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
		//[-777, -9, -8, -5, -4, -3, 1, 3, 7]
		//		耗时:3
	}

}

递归:

java">package com.m.suan_pai;


import java.util.LinkedList;
import java.util.List;

public class Test {

    public static void quickSort1(List<Integer> list, int left, int right) {
        if (left < right) {
            dealPivot1(list, left, right);

            int pivot = right - 1;
            int i = left;
            int j = pivot;

            while (true) {
                while (list.get(++i) < list.get(pivot)) {
                }
                while (j > left && list.get(--j) > list.get(pivot)) {
                }
                if (i < j) {
                    swap1(list, i, j);
                } else {
                    break;
                }
            }
            if (i < right) {
                swap1(list, i, right - 1);
            }
            dealPivot1(list, left, i - 1);
            dealPivot1(list, i + 1, right);
        }
    }

    public static void dealPivot1(List<Integer> list, int left, int right) {
        int mid = (left + right) / 2;
        if (list.get(left) > list.get(right)) {
            swap1(list, left, right);
        }
        if (list.get(left) > list.get(mid)) {
            swap1(list, left, mid);
        }
        if (list.get(mid) > list.get(right)) {
            swap1(list, mid, right);
        }

        swap1(list, mid, right - 1);
    }

    public static void swap1(List<Integer> list, int a, int b) {
        int t = list.get(a);
        list.set(a, list.get(b));
        list.set(b, t);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{34, 56, 3, 43, 54, 23, 42};

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (Integer i : arr) {
            linkedList.add(i);
        }
        quickSort1(linkedList, 0, linkedList.size() - 1);
        System.out.println(linkedList);
    }


}

快排不适合同于链表，但是可以实现，时间复杂度为o（nlgn）

平均时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1））

分析：由于单链表是没有prev指针的，所以跟数组一样的low，high指针就不适合单链表

对链表进行归并排序

我们对链表进行排序，使用归并排序来进行排序，时间复杂度O(nlgn)。

此种方式的排序主要涉及到以下三个知识点：

1. 两个链表的归并；

2. 归并排序的思想；

3. 获取一个链表的中间结点；

我的归并排序代码如下

java">package com.m.suan_pai;


import java.lang.reflect.InvocationTargetException;
import java.util.LinkedList;
import java.util.List;

public class Test {

    public static void mergeSort(List<Integer> list) {
        try {

            List<Integer> list1 = list.getClass().getConstructor().newInstance();

            mergeSort(list,0,list.size()-1,list1);

        } catch (NoSuchMethodException e) {
            e.printStackTrace();
        } catch (InstantiationException e) {
            e.printStackTrace();
        } catch (IllegalAccessException e) {
            e.printStackTrace();
        } catch (InvocationTargetException e) {
            e.printStackTrace();
        }
    }

    public static void mergeSort(List<Integer> list, int left, int right, List<Integer> list2) {
        if(left < right){
            int mid = (left+right)/2;

            //使左子树有序
            mergeSort(list,left,mid,list2);

            //使右子树有序
            mergeSort(list,mid+1,right,list2);

            //合并左右子树
            merge(list,left,mid,right,list2);
        }
    }

    public static void merge(List<Integer> list, int left, int mid,int right, List<Integer> list2) {
        int index = 0;
        int i = left;
        int j = mid+1;

        while (i<=mid && j<=right){
            if(list.get(i)<list.get(j)){
                list2.add(index++,list.get(i++));
            }else{
                list2.add(index++,list.get(j++));
            }
        }

        while (i<=mid){
            list2.add(index++,list.get(i++));
        }

        while (j<=right){
            list2.add(index++,list.get(j++));
        }

        index = 0;

        while (left <= right){
            list.set(left++,list2.get(index++));
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{34, 56, 3, 43, 54, 23, 42};

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (Integer i : arr) {
            linkedList.add(i);
        }
        mergeSort(linkedList);
        System.out.println(linkedList);
    }


}