精华内容
下载资源
问答
  • 快速排序算法Java实现 1 算法概念。 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。 2 算法思想。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一...

    快速排序算法Java实现

    1 算法概念。
    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
    2 算法思想。
    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    3 实现思路。
    ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,…,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
    ②把左区作为一个整体,用①的步骤进行处理,右区进行相同的处理。(即递归)
    ③重复第①、②步,直到左区处理完毕。
    4 代码实现(递归方式)

    static void quicksort(int n[], int left, int right) {
    	int dp;
    	if (left < right) {
    		dp = partition(n, left, right);
    		quicksort(n, left, dp - 1);
    		quicksort(n, dp + 1, right);
    	}
    }
    
    static int partition(int n[], int left, int right) {
    	int pivot = n[left];
    	while (left < right) {
    		while (left < right && n[right] >= pivot)
    			right--;
    		if (left < right)
    			n[left++] = n[right];
    		while (left < right && n[left] <= pivot)
    			left++;
    		if (left < right)
    			n[right--] = n[left];
    	}
    	n[left] = pivot;
    	return left;
    }
    

    5 代码实现(非递归方式)

    package sort.algorithm;
    import java.util.Stack;
    //快速排序的非递归实现,利用系统的栈stack
    public class QuickSortNonRecursion {
     public static void main(String[] args) {
    	 QuickSortNonRecursion qsnr = new QuickSortNonRecursion();
    	 int[] array = {0, 2, 11, 121, 18, 99, 3, 5, 101, 22, 9, 100};
    	 qsnr.quicksort(array);
    	  for (int i : array) {
    			System.out.print(i + "  ");
    	  }
    	}
    			 
    	public void quicksort(int[] array) {
    		if (array == null || array.length == 1) return;
    		//存放开始与结束索引
    		Stack<Integer> s = new Stack<Integer>(); 
    		//压栈       
    		s.push(0); 
    		s.push(array.length - 1); 
    		//利用循环里实现
    		while (!s.empty()) { 
    			int right = s.pop(); 
    			int left = s.pop(); 
    			//如果最大索引小于等于左边索引,说明结束了
    			if (right <= left) continue; 
    					 
    			int i = partition(array, left, right); 
    			if (left < i - 1) {
    				s.push(left);
    				s.push(i - 1);
    			} 
    			if (i + 1 < right) {
    				s.push(i+1);
    				s.push(right);
    			}
    		} 
    	}
    	//找到轴心,进行交换
    	public int partition (int[] data, int first, int end)
    	{
    		int temp;
    		int i=first,j=end;
    		if(first<end)
    		{
    			temp=data[i];
    			//当i=j的时候,则说明扫描完成了
    			while(i<j)
    			{
    				//从右边向左边扫描找到一个小于temp的元素
    				while(j>i&&data[j]>temp)j--;
    				if(i<j)
    				{
    					//将该元素赋值给temp
    					data[i]=data[j];
    					//赋值后就应该将i+1指向下一个序号
    					i++;
    				}
    					   
    				//然后从左边向右边开始扫描,找到一个大于temp的元素
    				while(i<j&&temp>data[i])i++;
    				if(i<j)
    				{
    					//将该元素赋值给temp
    					data[j]=data[i];
    					//赋值后就应该将j-1指向前一个序号
    					j--;
    				}
    			}
    			//将轴数据放在i位置中
    			data[i]=temp;
    		}
    		return i;
    	}
    }
    
    展开全文
  • 快速排序算法Java详解

    万次阅读 2014-11-08 16:17:13
    在实际应用中,一个经过仔细调整的快速排序算法应该在大多数计算机上运行的比其他排序算法要快的多,对于大型文件,快速排序的性能是希尔排序的5到10倍,它还能更搞笑的处理在实际问题中遇到的其他类型的文件。...

    快速排序是一种分治排序的算法,将数组划分为两个部分,然后分别对两个部分进行排序。在实际应用中,一个经过仔细调整的快速排序算法应该在大多数计算机上运行的比其他排序算法要快的多,对于大型文件,快速排序的性能是希尔排序的5到10倍,它还能更搞笑的处理在实际问题中遇到的其他类型的文件。所以快速排序是在找工作面试中被问到的最多的一个排序算法,比如快速排序的基本思想、时间复杂度、稳定性、快速排序的改进等。

    这篇文章主要介绍快速排序的基本算法及其优化等。关于其他基本的排序算法见:基本排序算法Java详解


    1 快速排序的基本算法

    快速排序的基本思想是:通过一趟排序将待排序的记录分隔成独立的两个部分,其中一部分记录的关键字均比另一部分记录的关键字小,接着分别对两部分分别进行同样的操作,最终得到有序的结果。

    一趟快速排序的具体做法如下代码:变量v作为一个旗帜(枢轴),保存了元素items[r],i和j分别从左边和右边向内部扫描,扫描过程中保证:i的左边没有比v大的,j的右边没有比v小的。一旦两个指针相遇,就交换a[i]和a[r],即将v赋值给a[i],这样v左侧的元素都小于等于v,v右边的元素都大于等于v,结束了划分过程。

    private int partition(int[] items, int l, int r) {
    	int i = l - 1, j = r;
    	int v = items[r];
    	while(true) {
    		while(items[++i] < v);
    		while(v < items[--j])
    			if(j ==l) break; //防止划分元素v是文件中最小的元素
    		if(i >= j) break;
    		exchange(items, i, j);
    	}
    	exchange(items, i, r);
    	return i;
    }

    其元素下标形式如下图所示:


    根据上述代码,一趟排序的示意图如下图所示:


    上述只是为一趟快速排序的过程,其整个快速排序的过程可以采用递归形式,递归形式的快速排序算法如下所示:

    public void sort(int[] items, int l, int r) {
    	if(l >= r) return; //返回,不用排序
    	
    	int i = partition(items, l, r);
    	
    	sort(items, l, i-1); //递归排序
    	sort(items, i+1, r); //递归排序
    }

    快速排序最坏的时间复杂度为O(n^2),平均时间复杂度为O(nlogn)。


    2 快速排序非递归算法(栈)

    快速排序的递归算法使用一个由程序自动创建的隐式栈,非递归算法使用显式栈。

    快速排序过程中首先把数组的后部和前部的下标推入栈,如下图的7和0两个下标进栈。然后进入循环:取出栈的两个元素,将这两个 元素作为数组下标,对这段数组中的数 进行一趟快速排序,排序后再把两部分的前后下标压入栈,如下图的5、7、0、3进栈。


    在实际应用中,为了使栈的大小保证在lgN范围内,在入栈时会检测两边文件的大小,把较大的一边优先入栈,较小的一边后入栈(在下面代码中有体现)。

    利用栈的非递归快速快速排序代码如下:

    public void sort_stack(int[] items, int l, int r) {
    	int i;
    	push2(r, l); //向栈推入r和l
    	
    	while(!stackempty()) { //只要栈不空就一直循环
    		l = pop(); r = pop();
    		if(r <= l) continue;
    		i = partition(items, l, r);
    		//较大的一侧先入栈,可以保证栈的最大深度在lgN以内
    		if(i-l > r-i) {
    			push2(i-1, l); push2(r, i+1);
    		} else {
    			push2(r, i+1); push2(i-1, l);
    		}
    	}
    }


    其完整代码如下:

    public class QuickSort {
    	private Stack<Integer> stack = new Stack<Integer>();
    	
    	/**
    	 * 利用栈的非递归快速排序
    	 * @param items
    	 * @param l
    	 * @param r
    	 */
    	public void sort_stack(int[] items, int l, int r) {
    		int i;
    		push2(r, l); //向栈推入r和l
    		
    		while(!stackempty()) { //只要栈不空就一直循环
    			l = pop(); r = pop();
    			if(r <= l) continue;
    			i = partition(items, l, r);
    			//较大的一侧先入栈,可以保证栈的最大深度在lgN以内
    			if(i-l > r-i) {
    				push2(i-1, l); push2(r, i+1);
    			} else {
    				push2(r, i+1); push2(i-1, l);
    			}
    		}
    	}
    	
    	//依次向栈推入a和b
    	private void push2(int a, int b) {
    		stack.push(a);
    		stack.push(b);
    	}
    	
    	private boolean stackempty() {
    		return stack.isEmpty();
    	}
    	
    	private int pop() {
    		return stack.pop();
    	}
    
    	//对下标从l到r之间的items进行处理:
    	private int partition(int[] items, int l, int r) {
    		int i = l - 1, j = r;
    		int v = items[r];
    		while(true) {
    			while(items[++i] < v);
    			while(v < items[--j])
    				if(j ==l) break;
    			if(i >= j) break;
    			exchange(items, i, j);
    		}
    		exchange(items, i, r);
    		return i;
    	}
    	
    	//交换
    	private void exchange(int[] items, int a, int b) {
    		int t;
    		t = items[a];
    		items[a] = items[b];
    		items[b] = t;
    	}
    	
    	//测试
    	public static void main(String[] args) {
    		int[] items = {12, 21, 13, 12, 11, 15, 17, 22};
    		
    		QuickSort qs = new QuickSort();
    		qs.sort_stack(items, 0, items.length-1);
    		
    		for(int i=0; i<items.length; i++) {
    			System.out.print(items[i] + " ");
    		}
    	}
    }
    


    3 快速排序的改进

    3.1 小的子文件

    快速排序在针对大文件(数组长度很长)有很大的优势,但是对于小文件其优势将被削弱。对于基本的快速排序中,当递归到后面时程序会调用自身的许多小文件,因而在遇到子文件时尽可能使用好的方法,来对快速排序进行改进。一种方法是在递归开始前进行测试,当文件太小时就用其他排序方式,即将return改为调用插入排序(小文件使用插入排序较好,根据自于《算法:C语言实现》)。如下:

    if(r-l <= M) insertionSort(items, l, r);  //根据《算法:C语言实现》的实验验证,M取10为宜,insertionSort()为插入排序

    考虑小的子文件后的优化的快速排序代码为:

    private static final int M = 10;
    private void quickSort(int[] items, int l, int r) {
    	if(l >= r) return; //不用排序
    	if(r - l <= M) return; //******小的文件,不用排序*****
    	
    	int i = partition(items, l, r);
    	
    	quickSort(items, l, i-1); //递归排序
    	quickSort(items, i+1, r); //递归排序
    }
    
    public void sort(int[] items, int l, int r) {
    	quickSort(items, l, r);
    	insertionSort(items, l, r); //*****插入排序*****
    }
    (其中的插入排序算法可参见:基本排序算法Java详解

    3.2 三者取中算法改进

    由于快速排序在记录有序或基本有序时,将退化为冒泡排序,其事件复杂度为O(n^2)。解决办法就是使用尽一个可能在文件中间划分的元素。可采用”三者取中“的法则来选择旗帜(枢轴)记录,即比较数组的左边元素(items[l])、中间元素(items[(l+r)/2])和右边元素(item[r]),取三者中中间大小的元素作为旗帜(枢轴)记录。

    三者取中算法在下面几个方面进行了改进。首先,它使得最坏情况在实际排序中几乎不可能发生。其次,它减少了划分对观察哨的需要。最后,它使总的平均运行时间大约减少了5%。(这段话来自于《算法:C语言实现》)

    三者取中法和小的子文件优化结合起来可以将原始的递归实现的快速排序算法运行时间提高20%~25%(根据《算法:C语言实现》)。下面这段代码就是三者取中和小的子文件相结合的优化算法:


    private void quickSort(int[] items, int l, int r) {
    	if(l >= r) return; //不用排序
    	
    	if(r - l <= M) return; //小的文件,被忽略
    	exchange(items, (l+r)/2, r-1);
    	compexch(items, l, r-1);
    	compexch(items, l, r);
    	compexch(items, r-1, r);
    	//经过以上三步就完成了对l、(l+r)/2、r三个元素的排序。((l+r)/2元素放在r-1位置上)
    	
    	//与普通的快速排序也有不同,划分的时候第l个和第r个不用考虑了
    	//因为第l个元素一定小于“旗帜(枢轴)元素”,第r个元素一定大于“旗帜(枢轴)元素”
    	//“旗帜(枢轴)元素”在r-1上。
    	int i = partition(items, l+1, r-1);
    	
    	quickSort(items, l, i-1); //递归排序
    	quickSort(items, i+1, r); //递归排序
    }
    	
    public void sort(int[] items, int l, int r) {
    	quickSort(items, l, r);
    	insertionSort(items, l, r); //插入排序
    }
    其中的辅助函数compexch()如下:

    private void exchange(int[] items, int a, int b) {
    	int t;
    	t = items[a];
    	items[a] = items[b];
    	items[b] = t;
    }
    
    private void compexch(int[] items, int a, int b) {
    	if(items[b] < items[a])
    		exchange(items, a, b);
    }

    此外,我们还可以消除递归、用内嵌代码代替函数、使用观察哨等方式继续对程序进行改进,这里就不详细介绍了。


    全文完。

    展开全文
  • 快速排序算法java版实现

    千次阅读 2017-06-02 16:19:11
    本文使用java实现快速排序

    快速排序思想:从待排序序列中找到一个关键字(默认为第一个元素) 然后将比关键字少的数据排列在左边,大于关键字的排在右边,然后对关键字左右两边的序列继续上面步骤,直至关键字两边的序列都已经排好序。具体算法如下:

    设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,

     

     然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
     值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
     一趟快速排序的算法是:
     1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
     2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
     3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
     4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
     5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,
     4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。

     

      找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

    来源于百度百科。

    java代码实现:

     

    package persistent.prestige.console.algorithm;
    
    /**
     * 
     * 
     * 设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,
     * 然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。
     * 值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。
     * 一趟快速排序的算法是:
     * 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
     * 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
     * 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
     * 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
     * 5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,
     * 4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。
     * 找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
    
     * 
     * 
     * @author lenovo
     *
     */
    public class QuickSort {
    	
    	
    	public static final void quickSort(int[] a, int low, int hign ) {
    		if(hign <= low) return; // 如果hign 小于等于 low ,说明待排序队列只包含一个元素,无法再排序
    		
    		int keyIdx = asort(a, low, hign); 
    		
    		if( ! (keyIdx == low && low == hign) ) { // keyIdx == low && low == hign 则说明不可分
    			if(keyIdx == low ) { //说明左边已经排好序了
    				quickSort(a, low + 1, hign);
    			} else if  (keyIdx == hign ) {  // 说明右边已经排序好了
    				quickSort(a, low, hign -1);
    			} else {
    				quickSort(a, low , keyIdx -1); // 关键字左边排序
    				quickSort(a, keyIdx + 1, hign); // 关键字右边排序
    			}
    		}
    		
    	}
    	
    	
    	/**
    	 * 快速排序   一趟排序算法实现
    	 * 一趟快速排序的算法是:(来源于百度百科)
    	 * 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
    	 * 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
    	 * 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;
    	 * 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
    	 * 5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,
    	 * 4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。
    	 * 找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
    	 * 
    	 * @param a			待排序数组
    	 * @param low       待排序起始下标
    	 * @param hign      待排序结束下标  (low hign) 限制排序数组范围
    	 * @return          本轮排序后,关键字所在位置(下标)
    	 */
    	private static final int asort(int[] a, int low, int hign) {
     		int key = a[low];
    		
    		loop :
    		while (true) { // low 与 hign 相等时退出
    			while( hign > 0 ) {
    				
    				if( a[hign] < key ) {
    					swap(a, low, hign);   // 从后向前找,找到第一个比关键字小的元素后交换元素后跳出本次比较
    					break;
    				}
    				
    				hign --;
    				
    				if(low == hign) break loop;
    			}
    			
    			low ++; 
    			if(low == hign) break loop;
    			
    			while( low < a.length ) {
    				if( a[low] > key ) {   // 从前向后找,找到第一个比关键字大的元素时交换元素后跳出本次比较
    					swap(a, low, hign);
    					
    					break;
    				}
    				
    				low ++; 
    				if(low == hign) break loop;
    			}
    		}
    		return low;//关键字所在的位置
    	}
    
    	/**
    	 * 交换数组中两个元素的位置
    	 * @param a
    	 * @param i
    	 * @param j
    	 */
    	private static void swap(int[] a, int i, int j) {
    		int tmp = a[i];
    		a[i] = a[j];
    		a[j] = tmp;
    	}
    	
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		
    		System.out.println("待排序数据:(5,8,2,10,6,9,21,18,19,7)");
    		int[] a = new int[] {5,8,2,10,6,9,21,18,19,7};
    		quickSort(a, 0, a.length -1);
    		System.out.println("排序后结果:");
    		for(int i : a) {
    			System.out.print(i + " ");
    		}
    		
    		
    		System.out.println(" ---------------------");
    		
    		System.out.println("待排序数据:(5,8,2,10,5,9,21,18,8,7)");
    		a = new int[] {5,8,2,10,5,9,21,18,8,7};
    		quickSort(a, 0, a.length -1);
    		System.out.println("排序后结果:");
    		for(int i : a) {
    			System.out.print(i + " ");
    		}
    
    	}
    	
    	
    	
    
    }
    

    算法复杂度分析等相关知识,后续补上。先继续归并排序算法的代码实现先。

    欢迎加笔者微信号(dingwpmz),加群探讨,笔者优质专栏目录:

    1、源码分析RocketMQ专栏(40篇+)
    2、源码分析Sentinel专栏(12篇+)
    3、源码分析Dubbo专栏(28篇+)
    4、源码分析Mybatis专栏
    5、源码分析Netty专栏(18篇+)
    6、源码分析JUC专栏
    7、源码分析Elasticjob专栏
    8、Elasticsearch专栏
    9、源码分析Mycat专栏

    展开全文
  • 【该改进的算法是在本人已有快排算法的基础上改进的:快速排序】 (广泛阅读网上资料整理所得,其中重要参考博客:传送门——感谢!) 尽管基本的快速排序已经很有用处了,但是有些情况下,基本的快速排序可能会...

    快速排序

    【该改进的算法是在本人已有快排算法的基础上改进的:快速排序

    (广泛阅读网上资料整理所得,其中重要参考博客:传送门——感谢!)

    尽管基本的快速排序已经很有用处了,但是有些情况下,基本的快速排序可能会极为低效,比如排序一个大小为N的有序序列,这样所有的划分就会退化,程序会调用自身N次,所以

    ·快速排序最坏情况下使用大约(N^2)/2次比较

    我们可以对快速排序进行改进,有以下几种方法:

    1. 切换到插入排序

    通过观察可见,快速排序的递归调用自身许多的小序列,所以我们可以在遇到小的子序列的时候可以用更好的方法,以此来对快速排序进行改进,比如在子序列小于某个值M时进行插入排序,方法就是把递归出口的条件换成下面这样:

    其中M的值根据情况调整。

    【通过实验可以证明,当对于多个重复区间操作递归时,发生了栈溢出,而调整M的参数可以有效避免错误。如下图只有M值发生了变化】

    2.三路划分的快速排序

    对于处理含有大量重复元素的序列,采用原来的方法会产生不必要的操作。我们可以在基准值调整位置的时候,把与基准值相等的放到数组的两端(原来在左边的放左端,原来的右边的放右端)。最后在基准值确定位置的时候,把两端的与基准值相等的元素移动到基准值旁边。这样可以避免关于此基准值多余的操作。

    设置两个变量来记录两端的数量:

    接着按如上所说:

     

    3.三者取中划分

    对快速排序算法的另一种改进就是使用一个尽可能在序列中间划分的元素,即基准值key的大小最好是在待排序文件中不大不小

     

    有以两种思路:

    ·一种是避免最坏的情况,使用数组中的一个随机元素作为划分元素,这样出现最坏情况的几率就会相对很小

    ·一种是从序列中取出三个元素,使用三个元素的中间元素作为划分元素

     

    我们这里用的是第二种思路方法,取出数组的左边元素,中间元素和右边元素,然后对这三个元素进行排序,然后以中间的元素作为基准值key。


    完整代码如下:

    
    public class QuicksortSup {
    
    	public static void main(String[] args) {
    		int[] arr = {4,1,4,4,4,5,2,2,2,2,2,7,5,6,4,4,4,4,4,0,9};
    		int len = arr.length;
    		
    		//从小到大快速排序
    		quickSort(arr, 0, len-1);
    		
    		for(int i=0; i<len; i++) {
    			System.out.print(arr[i]+" ");
    		}
    		System.out.println();
    	}
    
    	private static void quickSort(int[] arr, int l, int r) {
    		if(l >= r) return ; //只有一个元素或不合法时返回
    		
    		/*
    		 * 改进一:对于少量区间更换更好的排序方法
    		 */
    		int M = 8;
    		if(r - l < M) {
    			InsertionSort(arr, l, r);//1.插入排序
    			return ;
    		}
    		
    		int i = l;
    		int j = r;
    		
    		/**
    		 * 改进三:选取区间的三个值,排序后去中间值当基准值
    		 * (为了不影响原来算法的书写,所以把取得的中间值移动到最左端)
    		 */
    		int mid = l + ((r - l) >> 1);
    		if(arr[l] > arr[mid]) swap(arr, l, mid);
    		if(arr[l] > arr[r]) swap(arr, l, r);
    		if(arr[mid] > arr[r]) swap(arr, mid, r);
    		
    		swap(arr, l, mid);
    		int key = arr[l]; //3.基准值
    		
    		/**
    		 * 改进二:对于与基准值相等的最后移到数组中间,不再参与递归
    		 */
    		int lLen = l;//2.左区间与基准值相等的标志
    		int rLen = r;//2.右区间与基准值相等的标志
    		
    		while(i < j) {
    			while(i < j && arr[j] >= key) //从后开始往回找
    				j --;
    			while(i < j && arr[i] <= key)
    				i ++;
    			if(i < j)
    				swap(arr, i, j);
    			
    			//2.把与基准值相等的放到区间两端
    			if(arr[i] == key) {
    				swap(arr, i, lLen);
    				lLen ++;
    			}
    			if(arr[j] == key) {
    				swap(arr, j, rLen);
    				rLen --;
    			}
    		}
    		//与基准值交换
    		swap(arr, i, l); 
    		
    		//2.使区间两端与基准值相等的元素移动到基准值位置附近
    		for(int u=l; u<lLen; u++) {
    			swap(arr, u, --i);
    		}
    		for(int v=r; v>rLen; v--) {
    			swap(arr, v, --j);
    		}
    		
    		quickSort(arr, l, i-1);
    		quickSort(arr, i+1, r);
    	}
    	
    	private static void InsertionSort(int[] arr, int l, int r) {
    		for(int i=l+1; i<=r; i++) { //要插入的元素下标
    			for(int j=l; j<i; j++) {
    				if(arr[i] < arr[j]) {
    					swap(arr, i, j);
    				}
    			}
    		}
    	}
    
    	private static void swap(int[] arr, int i, int j) {
    		int t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
    	}
    
    }
    

    如有错误或者不合理的地方,敬请指正~

    加油!!

     

    展开全文
  • 简单的快速排序算法 java版本

    千次阅读 2019-06-04 11:04:57
    简单的快速排序算法一、代码二、 一、代码 凡事先上代码 import java.util.*; class QuickSort1 { private static void quickSort(int[] a, int lo, int hi) { if (lo >= hi) return; int pivot = partition...
  •  System.out.println("快速排序算法:");  System.out.print("原始数据: ");  for(int i = 0;i;i++){  System.out.print(arm[i]+" ");  }  System.out.println("");  QuickSort.QuickSort(arm);  System....
  • 快速排序算法Java

    万次阅读 2018-05-04 18:37:41
    快速排序,是实践中的一种快速的排序算法,在C++和java基本类型的排序中特别有用,它的平均运行时间是O(NlogN)。该算法之所以特别快,主要是由于非常精炼和高度优化的内部循环。它的最坏情形性能为O(N²),但经过...
  • java快速排序算法

    千次阅读 2018-09-07 16:33:22
    快速排序算法写法很多种,这里介绍一种简单的: //递归方式实现快速排序 //算法思想每次排序会把小于锚点的数放在左边,大于锚点的数放在右边, //排完一轮就找到了锚点的正确位置,然后递归对锚点左侧,和右侧的...
  • 合并排序、自然合并排序与快速排序算法Java实现
  • 快速排序算法Java实现)

    千次阅读 2016-12-08 22:48:44
    java实现快速排序(简述)
  • 快速排序算法(Java)

    千次阅读 2016-06-12 17:32:00
     快速排序(Quicksort)是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,...
  • 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更...
  • 十大排序算法快速排序Java实现

    万次阅读 2020-07-19 14:10:11
    快速排序 快速排序(Quick Sort)是对冒泡排序的一种改进,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数。 快速排序在1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare...
  • 快速排序算法原理及Java代码实现1 基本思想1.1 意义1.2 简单解释1.3 基本思想1.4 图示2 Java代码实现快速排序 1 基本思想 1.1 意义 快速排序是冒泡排序的改进版,也是最好的一种内排序,还涉及到分治和递归 1.2 简单...
  • java:快速排序算法与冒泡排序算法

    千次阅读 2014-11-05 12:42:12
    算法,冒泡排序算法,快速排序算法
  • Java实现快速排序算法

    千次阅读 2018-07-15 21:35:44
    快速排序算法的思想是:在数组中选取一个数(一般都是选第一个数),分别与其它的每一个数比较,把比这个数小的数放到它的前面,比他大的数放到它的后面,此时数组分成两部分,该数前面的都比它小,后面的都比它大,...
  • 欢迎转载,请注明出处: 最近马上要校招了,重新熟悉一下数据结构和一些常用算法还是...今天我们来看一下快速排序: public class QuickSort { public static void quickSort(int n[],int low ,int high){ if (low )
  • 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。...
  • 快速排序算法的三种方式及其优化java实现1、快速排序算法的简绍2、快速排序的基本思想3、快速排序左右指针法图解4、快速排序左右指针法核心代码5、快速排序挖坑法图解6、快速排序挖坑法核心代码7、快速排序前后指...
  • 最近想学点分类算法,在写决策树算法的时候对于连续变量要先进行排序,于是就先写了一个快排的算法。思路照着百度百科上的C语言版本学的,但是由于java中没有指令的存在,... * 快速排序 * @author Multiangle from S
  • Java算法基础之快速排序算法

    千次阅读 2017-02-19 23:11:03
    所谓的快速排序的思想就是,首先把数组的第一个数拿出来作为一个key,在前后分别设置一个i,j作为标识,然后拿这个数组从后面往前遍历, 及j- -,直到找到第一个小于这个key的那个数然后交换这两个值,交换完成后,...
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
  • 图文讲解QuickSort快速排序算法Java版)

    万次阅读 多人点赞 2016-11-30 14:28:54
    什么是快速排序快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据...
  • 排序算法Java实现

    千次阅读 2016-04-16 21:55:49
    排序算法Java实现排序算法的分类: 内部排序,在排序过程中,全部记录放在内存中,称为内部排序; 外部排序,在排序过程中需要使用外部存储(磁盘),则称为外部排序。 主要介绍内部排序: 插入排序:直接插入排序、...
  • java快速排序算法

    千次阅读 2007-10-11 14:51:00
    快速排序算法. 快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行...
  • 实现快速排序算法的关键在于先在数组中选择一个数字,接下来把数组中的数字分为两部分,比选择数字小的数字移动到数组的左边,比选择数字大的数字移动到数组的右边。 具体的实现算法为: 设要排序的数组是A[0]……...
  • 使用Java和Python实现快速排序算法

    千次阅读 2020-02-02 21:59:57
    快速排序采用了分而治之的策略(divide and conquer,D&C),一种著名的递归式问题解决方法。 分而治之的工作原理: 找出简单的基线条件 确定如何缩小问题的规模,使其符合基线条件 使用递归实现数组元素求和: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 103,699
精华内容 41,479
关键字:

快速排序算法java

java 订阅