实现代码如下:原理是利用了快速排序‘分治’思想,判断左边区域的大小是否在1000范围之内,如果是就丢弃右边区域的递归调用,从而减少了递归和循环的调用。
测试结果:长度为1000w的数组,在30-200ms以内完成。
测试环境:window xp ,Celeron双核cpu 2.19GHZ,2G内存。
public static void _sort( int[] arr , int left , int right ){ if( left >= right ) return; int markIndex = right; int markVal = arr[markIndex]; int lt = left - 1; int rt = right; while( true ){ while( arr[++lt] < markVal ); while( rt > left && arr[--rt] > markVal ); if( lt >= rt ) break; swap( arr , lt , rt ); } swap( arr , lt , markIndex ); // if( (arr.length - 2 - lt) < 1000 ) _sort( arr , left , lt-1 ); if( lt < 1000 ) _sort( arr , lt+1 , right ); } private static void swap( int[] arr , int lt , int rt ){ int temp = arr[lt]; arr[lt] = arr[rt]; arr[rt] = temp; } public static void sort( int[] arr ){ _sort( arr , 0 , arr.length-1 ); }
相关推荐
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
leetcode 答案 leetcode-prictise 领扣算法练习 基础部分 基础排序部分 冒泡排序:对相邻的两个元素进行比较,如果满足大小要求,就将这两个数据交换位置,...快速排序:快速排序使用分治法(Divide and conquer)策略
一部久享盛誉的程序开发宝典。精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后...
一部久享盛誉的程序开发宝典。精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后...
一部久享盛誉的程序开发宝典。精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后...
一部久享盛誉的程序开发宝典。精选570个典型范例,全面覆盖实用和热点技术,涉及面广,实用性强源于实际项目开发,帮助读者短时间掌握更多实用技术,提高编程水平范例经过精心编排,重点、难点突出,易学易懂书后...
内容及步骤: 1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,...