JAVA实现单链表快速排序_java单链表快速排序

链表与数组排序的不同在于，数组里通过下标交换的开销是O(1)的，而链表是O(n)的。所以，直接照搬数组的快速排序到链表，速度会很慢。

但是链表有一个优点，就是把元素移动到尾部，时间是O(1)的。

思路如下：

将链表的第一个元素设置为pivot，遍历之后的n-1个元素，如果该元素的值大于pivot，则将其放在链表末尾（O(1)时间）。遍历所需时间是O(n)的。遍历之后，数组分为三个部分：【pivot】【比pivot小的元素】【比pivot大的元素】，将pivot插入后两部分中间，得到：【比pivot小的元素】【pivot】【比pivot大的元素】，此时，就可以对前后两部分进行递归了。算法复杂度为O（nlog(n)）。

注意：quick_sort的三个参数分别为：start_pre,指向第一个元素的Node（即start_pre.next=start），len是链表的长度，end是尾指针（注意，end.next不一定为null）

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
 
public class LinkListSort {
	public static int [] random_order_array(int len){  
        List <Integer> list = new ArrayList<Integer>();  
        for (int i = 0; i < len; i ++){  
            list.add(i);  
        }  
        Collections.shuffle(list);  
        int [] array = new int [len];  
        for (int i = 0; i < len; i ++)  
            array[i] = list.get(i);  
        return array;  
    }  
	
	public static void print_mynode(MyNode node, int len){
		MyNode temp = node;
		for (int i = 0; i < len; i ++){
			System.out.print(temp.val + " ");
			temp = temp.next;
		}
		System.out.println();
	}
	
	public static void quiksort(MyNode start_pre, int len, MyNode end){
		if (len <= 1)
			return;
		MyNode start = start_pre.next;
		int pivot_val = start.val;
		int split_position = 0;
		
		MyNode temp0 = start;
		MyNode temp1 = start.next;
		for (int i = 1; i < len; i ++){
			if (temp1.val > pivot_val){ //放到链表末尾
				if (temp1 != end){
					temp0.next = temp1.next;
					temp1.next = end.next;
					end.next = temp1;
					end = temp1;
					temp1 = temp0.next;
				}
			}
			else{
				temp1 = temp1.next;
				temp0 = temp0.next;
			
				split_position ++;
			}
		}
		MyNode pivot_node = start;
		if (temp0 != start){
			start_pre.next = pivot_node.next;
			temp0.next = pivot_node;
			pivot_node.next = temp1;	
		}
		quiksort(start_pre, split_position, temp0);
		quiksort(pivot_node, len - split_position - 1, end);
	}
	
	public static void main(String [] args){
		
		int len = 20;
		int [] array = random_order_array(len);
		//int [] array = {0, 3, 2, 8, 6, 9, 7, 5, 1, 4 };
		//int [] array = {3, 2, 8, 6, 9, 7, 5, 1, 4  };
		MyNode start = new MyNode(array[0]);
		MyNode temp = start;
		for (int i = 1; i < array.length; i ++){
			temp.next = new MyNode(array[i]);
			temp = temp.next;
		}
		MyNode end = start;
		for (int i = 0; i < len - 1; i ++){
			end = end.next;
		}
		MyNode start_pre = new MyNode(-1);
		start_pre.next = start;
		System.out.println("乱序数组：");
		print_mynode(start_pre.next, len);
		quiksort(start_pre, len, end);
		System.out.println("排序后数组：");
		print_mynode(start_pre.next, len);
	}
}
 
class MyNode{
	int val;
	MyNode next = null;
	public MyNode(int val){
		this.val = val;
	}
}

输出结果举例：

乱序数组：
19 16 1 6 2 17 11 3 8 5 9 0 18 15 4 7 14 13 10 12 
排序后数组：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19