黑马程序员技术交流社区
标题:
Java排序算法总结
[打印本页]
作者:
Struggle_168
时间:
2015-4-12 10:54
标题:
Java排序算法总结
1、冒泡排序
冒泡排序是排序算法中最基本的一种排序方法，该方法逐次比较两个相邻数据的大小并交换位置来完成对数据排序，每次比较的结果都找出了这次比较中数据的最大项，因为是逐次比较，所以效率是O（N^2）的。
public void bubbleSort() {
int out,in;
for(out=index-1; out>1; --out) {
for(in=0; in<out; ++in) {
if(array[in]>array[in+1]) {
swap(in, in+1);
}
}
}
}
public void swap(int dex1, int dex2) {
int temp = array[dex1];
array[dex1] = array[dex2];
array[dex2] = temp;
}
2、选择排序
选择排序对冒泡排序进行了优化，在每次遍历比较的过程中不进行交换，而是记录本次遍历的最小值，在遍历结束后再将最小值移到这次遍历的开始位置。这样虽然比较次数没有改变，但交换的次数大大减少，一共只需要N次交换。因为比较的次数没变，所以效率任然是O（N^2）的。
[java] view plaincopy
public void selectionSort() {
int out, in;
for(out=0; out<index-1; ++out) {
int temp = out;
for(in=out+1; in<index; ++in) {
if(array[in] < array[temp]) {
temp = in;
}
}
swap(out, temp);
}
}
3、插入排序
插入排序充分利用已排列好的数据，然后将未排序的数据插入到已排数据的队伍当中，这样每插入一个未排序数据已排队伍都将增加一个成员，最终达到排序的目的。
[java] view plaincopy
public void insertionSort() {
int out ,in;
for(out=1; out<index; ++out) {
int temp = array[out];
in = out;
while(in>0 && temp<array[in-1]) {
array[in] = array[in-1];
--in;
}
array[in] = temp;
}
}
4、归并排序
归并排序是将两个有序数组合并为一个有序数组的排序，应用在一般排序上要结合二分法递归地将数组依次归并，最终得到一个大的有序数组。归并的效率是O（NlogN）的，但要额外开辟一个数组来存放临时数据，所以占用空间要大一倍。
[java] view plaincopy
public void mergeSort() {
int[] newArray = new int[index];
recMergeSort(newArray, 0, index-1);
}
private void recMergeSort(int[] data, int low, int upper) {
if(low == upper) {
return;
}
int mid = (low + upper)/2;
recMergeSort(data, mid+1, upper);
recMergeSort(data, low, mid);
merge(data, low, mid+1, upper);
}
private void merge(int[] data, int lowStart, int highStart, int upperBound) {
int j = 0;
int lowBound = lowStart;
int mid = highStart - 1;
int num = upperBound - lowStart + 1;
while(lowStart<=mid && highStart<=upperBound) {
if(array[lowStart] < array[highStart]) {
data[j++] = array[lowStart++];
} else {
data[j++] = array[highStart++];
}
}
while(lowStart<=mid) {
data[j++] = array[lowStart++];
}
while(highStart<=upperBound) {
data[j++] = array[highStart++];
}
for(j=0; j<num; j++) {
array[lowBound+j] = data[j];
}
}
5、希尔排序
希尔排序是一种高级排序，它是由插入排序进化来的，插入排序是将未排的数据依次与前面已排好的数据进行比较移动，这样如果一个较小的数排在靠后的位置，那么要找到这个数的正确位置就要进行较多次移动。希尔排序改进了这种方式，它将每次比较的间隔扩大，排过一次之后数据就分阶段有序了，之后逐渐缩小这个间隔再进行排序。这样做的目的就是让数据一开始可以在一个较大的范围内进行移动，待基本有序后数据的移动量就小了很多。
[java] view plaincopy
public void shellSort() {
int in, out;
int h = 1;
int temp;
while(h < index/3) {
h = h*3+1;
}
while(h>0) {
for(out=h; out<index; ++out) {
temp = array[out];
in = out;
while(in>h-1 && array[in-h] > temp) {
array[in] = array[in-h];
in -=h;
}
array[in] = temp;
}
h = (h-1)/3;
}
}
希尔排序中关键是对数据间隔h的选择，一个间隔序列是由Knuth提出的，即h=h*3+1，h的初始值为1，这是希尔排序中最优的间隔序列。
6、快速排序
快速排序是一种广泛使用的排序方法，效率可以达到O（NlogN），快速排序的原理是确定一个中间值pivot，将所有小于pivot的数据放在左侧，大于pivot的值放在右侧，之后再对左右两侧分别采取这种策略进行排序，直到这个过程结束。
[java] view plaincopy
private int partition(int left, int right, int pivot) {
int leftPtr = left;
int rightPtr = right-1;
while(true) {
while(array[++leftPtr] < pivot) ;
while(array[--rightPtr] > pivot);
if(leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr, right-1);
return leftPtr;
}
private int median(int left, int right) {
int center = (left+right)/2;
if(array[left]>array[center]) {
swap(left, center);
}
if(array[left]>array[right]) {
swap(left, right);
}
if(array[center]>array[right]) {
swap(center, right);
}
swap(center, right-1);
return array[right-1];
}
private void manulSort(int left, int right) {
int size = right-left+1;
if(size <= 1) return;
if(size == 2) {
if(array[left]>array[right]) swap(left, right);
} else {
if(array[left]>array[right-1]) swap(left, right-1);
if(array[left]>array[right]) swap(left, right);
if(array[right-1]>array[right]) swap(right-1, right);
}
}
private void recQuickSort(int left, int right) {
int size = right-left+1;
if(size<=3) {
manulSort(left, right);
} else {
int pivot = median(left, right);
int partition = partition(left, right, pivot);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
public void quickSort() {
recQuickSort(0, index-1);
}
快速排序的关键是确定中间值pivot，如果中间值选取的不好，会使快速排序的效率降到O（N^2）。上面的例子采用了三选一的策略来确定中间值，即在要排序的数据中选择左端、中间和右端三个数据后比较取中间值；还有在数据量较小时，比如小于三个则直接手动排序。
作者:
李永佳
时间:
2015-4-12 11:07
后四种排序方法，在视频中都没有讲解过，是自学的吗！楼主很强啊
作者:
xu921114
时间:
2015-4-12 11:08
数据结构里面的知识 顶一下
作者:
一袭蓝10
时间:
2015-4-12 11:18
佩服啊，后两种没有看懂
作者:
薛慧彬
时间:
2015-4-12 12:42
好像不需要都了解吧。。。。？
作者:
leonard
时间:
2015-4-12 12:43
总结的很好。赞。
作者:
时过境迁
时间:
2015-4-12 20:47
挺好，总结的不错
作者:
m-勇敢的心
时间:
2015-4-12 21:50
总结的很好啊
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2