快速排序的原理:
选一个数组中的第一个元素作为参照物,把所有小于参照物的元素都放在参照物的左边,将所有大于参照物的元素都放在右边。在递归的各自的子数组。
定义两个指针,分别从前遍历和从后遍历,向前遍历时,如果小于参照物,交换他们的位置,向后遍历时,如果大于参照物,交换他们的位置。直到两个指针相遇。
package calc;
public class QuickSort {
/**
* @param args
*/
public static void main(String[] args) {
int data[] = {110,305,65,57,90,120,110,8,79,44};
int min = 0;
int max = 9;
quickSort(data,min,max);
for(int temp : data)
System.err.println(temp);
}
public static void quickSort(int[] data,int min,int max){
int indexofpartition;
if(max>min){
//core
indexofpartition = findPartition(data,min,max);
quickSort(data,min,indexofpartition-1);
quickSort(data,indexofpartition+1,max);
}
}
public static int findPartition(int[] data,int min,int max){
int left,right,partitionIndex;
int temp,partitionelement;
partitionelement=data[min];
left=min;
right=max;
partitionIndex=min;
while(left<right){
while(data[right]>partitionelement&&left<right)
right--;
temp = data[right];
data[right] = data[partitionIndex];
data[partitionIndex] = temp;
partitionIndex = right;
while(data[left]<=partitionelement&&left<right)
left++;
if(left<right){
temp = data[left];
data[left] = data[partitionIndex];
data[left] = temp;
partitionIndex = left;
}
}
return partitionIndex;
}
}
归并排序
将一个数组分成两个数组,两个子数组再分两个子数组,直到每个子分组的元素个数都是1个,在将两个分组合并
左分组的元素和右分组元素比较,如果左的小就用左的,如果右的小就用右的。如果左分组或右分组有多余的元素,就直接添加到后面。
package calc;
public class MergeSort {
private static int count = 0 ;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] data = {110,305,65,57,90,120,110,8,79,44};
mergeSort(data,0,9);
for(int temp:data)
System.err.println(temp);
}
public static void mergeArray(int[] data,int left,int mid,int right){
int leftstart=left,leftend=mid;
int rightstart=mid+1,rightend=right;
int k = 0;
int size = right-left+1;
int[] temp = new int[size];
while(leftstart<=leftend&&rightstart<=rightend){
if(data[leftstart]>data[rightstart]){
temp[k++] = data[leftstart++];
}else{
temp[k++] = data[rightstart++];
}
}
while(leftstart<=leftend)
temp[k++] = data[leftstart++];
while(rightstart<=rightend)
temp[k++] = data[rightstart++];
for(int i=0;i<k;i++){
data[left+i] = temp[i];
}
}
public static void mergeSort(int[] data,int left,int right){
if(left<right){
int middle = (left+right)/2;
System.err.println((++count)+"次调用,middle:"+middle);
mergeSort(data,left,middle);
mergeSort(data,middle+1,right);
mergeArray(data,left,middle,right);
}
}
}
分享到:
相关推荐
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
本程序是关于快速排序的算法与归并排序,并比较两者所需的时间
算法设计实验报告,包括:快速排序和归并排序两种算法各自的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行截图,实验心得。
选择排序、插入排序、冒泡排序以及快速排序和归并排序的C语言实现,绝对可用
输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现频次最多的元素与排序后数组中前三大...
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
快速排序、归并排序、堆排序 并比较排序时间 数据结构与算法
自己编写的基于java的快速排序和归并算法
选择排序,冒泡排序,插入排序 基数排序,快速排序,归并排序
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
用matlab实现的快速排序以及归并排序
自己写的三个排序算法的比较。快速排序、归并排序、简单排序 对三个排序算法所消耗时间进行统计,比较时间效率 程序是在Linux下用C写的,vc下并未做测试。
插入排序、冒泡排序、归并排序、快速排序四种排序方式的C++实现,各写成了一个函数,主函数中可以选择调用那一个。初始化数组时用的是随机种子srand((int)time(0))。在宏中定义数组大小。