首页
登录 | 注册

Java: 实现顺序表和单链表的快速排序

快速排序

  • 快速排序原理

  快速排序(Quick Sort)的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序的目的。

  • 主程序
package Sort;

public class QuickSort {
	
	private void Qsort(int[] list, int low, int high){
		int privot;
		if(low < high) {
			print(list);
			/*算出枢轴值privot*/
			privot = Partition(list, low, high);
			/*对低子表递归排序*/
			Qsort(list, low, privot-1);
			/*对高子表递归排序*/
			Qsort(list, privot+1, high);			
		}
	}
	
	private int Partition(int[] list, int low, int high){
		/*用表的第一个记录做枢轴记录*/
		int privotkey = list[low];
		while (low < high){
			while (low < high && list[high] > privotkey)
				high--;			
			/*将比枢轴记录小的记录交换到低端*/
			swap(list, low, high);
			while (low < high && list[low] < privotkey)
				low++;
			/*将比枢轴记录大的记录交换到高端*/
			swap(list, low, high);			
		}
		/*返回枢轴所在的位置*/
		return low;
	}
	
	private void swap(int [] list,int j, int i){
		int temp;
		temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}	
	
	private void print(int[] data) {
		System.out.println("当前list数组的值:");
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + "\t");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] list = {50,40,80,30,60,70,10,90,20};
		QuickSort qs = new QuickSort();
		qs.Qsort(list, 0, list.length-1);
		qs.print(list);
	}
}

  

  • Qsort()分析
	private void Qsort(int[] list, int low, int high){
		int privot;
		if(low < high) {
			print(list);
			/*算出枢轴值privot*/
			privot = Partition(list, low, high);
			/*对低子表递归排序*/
			Qsort(list, low, privot-1);
			/*对高子表递归排序*/
			Qsort(list, privot+1, high);			
		}
	}

  

  • Partition()分析
	private int Partition(int[] list, int low, int high){
		/*用表的第一个记录做枢轴记录*/
		int privotkey = list[low];
		while (low < high){
			while (low < high && list[high] > privotkey)
				high--;			
			/*将比枢轴记录小的记录交换到低端*/
			swap(list, low, high);
			while (low < high && list[low] < privotkey)
				low++;
			/*将比枢轴记录大的记录交换到高端*/
			swap(list, low, high);			
		}
		/*返回枢轴所在的位置*/
		return low;
	}

  

  • 输出结果
当前list数组的值:
50	40	80	30	60	70	10	90	20	
当前list数组的值:
20	40	10	30	50	70	60	90	80	
当前list数组的值:
10	20	40	30	50	70	60	90	80	
当前list数组的值:
10	20	30	40	50	70	60	90	80	
当前list数组的值:
10	20	30	40	50	60	70	90	80	
当前list数组的值:
10	20	30	40	50	60	70	80	90	

  

  • 时间复杂度分析

  最优情况下,快速排序算法的时间复杂度为O(nlogn),空间复杂度也为O(nlogn)

  •  单链表快速排序实现
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode left = new ListNode(0), leftHead = left;
        ListNode right = new ListNode(0), rightHead = right;
        ListNode mid = new ListNode(0), midHead = mid;
        int val = head.val;
        
        while(head != null) {
            if(head.val < val) {
                left.next = head;
                left = head;
            } else if(head.val > val) {
                right.next = head;
                right = head;
            } else {
                mid.next = head;
                mid = head;
            }
            head = head.next;
        }
        
        left.next = null;
        right.next = null;
        mid.next = null;
        return merge(sortList(leftHead.next), midHead.next, sortList(rightHead.next));
    }
    
    public ListNode merge(ListNode left, ListNode mid, ListNode right) {
        ListNode leftTail = getTail(left);
        ListNode midTail = getTail(mid);
        midTail.next = right;
        if(leftTail != null) {
            leftTail.next = mid;
            return left;
        } else {
            return mid;
        }
    }
    
    public ListNode getTail(ListNode head) {
        if(head == null) return head;
        while(head.next != null) {
            head = head.next;
        }
        return head;
    }
}

  

 


相关文章

  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • final关键字可用于修饰类.方法和变量,final修饰的类不能被继承:final修饰的方法不可被重写:final修饰的变量不可被改变. 1. final类 final修饰的类不能被继承意思是final修饰的类不可以有子类,java.lan ...
  • java中常见的集合类大部分是非线程安全的,在多线程情况下会报并发修改异常(ConcurrentModificationException) 并发下的ArrayList类: 1 //集合类不安全的例子 2 public class Coll ...
  • java游戏开发杂谈
    线程,让游戏拥有了动态变化的能力. java的图形界面,在启动的时候,就开始了一个线程. 这个线程负责处理:JFrame.JPanel等的绘制.事件处理. 它是由操作系统调用的,在程序启动时开启,程序关闭时消亡. 这个线程里执行的逻辑,支撑 ...
  • 最近老师老是不讲新课,好繁!!! 还是来说抽象类吧. public abstract class A{ //因为下边有一个抽象方法,所以这就必须要是一个抽象类,要不然编译不能通过 public void c(){ System.out.pr ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.078 s.
京ICP备10005923号