2015-02-24
选择排序:
首先，找到数组中最小的那个元素
其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么他就和自己交换）
再次：在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。
如此往复，直到将整个数组排序。这种方法叫做选择排序
不断的选择剩余元素之中的最小者
package algorithms;
publicclass Sort {
privatestaticboolean less(Comparable v,Comparable w){
returnv.compareTo(w)<0;
}
privatestaticvoid exch(Comparable[] a,inti,intj){
Comparablet = a[i];
a[i] = a[j];
a[j] = t;
}
privatestaticvoid show(Comparable[] a) {
for(inti=0;i<a.length;i++){
System.err.print(a[i]+" ");
}
System.err.println();
}
privatestaticboolean isSorted(Comparable[] a) {
for(inti=1;i<a.length-1;i++){
if(less(a[i],a[i-1])){
returnfalse;
}
}
returntrue;
}
//选择排序
publicstaticvoid selectSort(Comparable[] a) {
for(inti=0;i<a.length;i++){
//将a[i]和a[i+1..a.length]中最小的元素交换
intmin = i;//最小元素的索引
for(intj=i+1;j<a.length;j++){
if(less(a[j],a[min])){
min = j;
}
exch(a, i, min);
}
}
}
//冒泡排序
privatestaticvoid BubbleSort(int[] a) {
inttemp=0;
for(inti=0;i<a.length-1;i++){
for(intj=0;j<a.length-1-i;j++){
if(a[j+1]<a[j]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
publicstaticvoid main(String[] args) {
String[]a = {"3","6","5","4","1","9","8","7","2"};
selectSort(a);
System.err.print("选择排序：");
assert isSorted(a);
show(a);
System.err.println("------------------------");
int[] b = {3,6,5,4,1,9,8,7,2};
BubbleSort(b);
System.err.print("冒泡排序：");
for(inti=0;i<b.length;i++){
System.err.print(b[i]+" ");
}
System.err.println();
}
}
没那么麻烦，粘上就能用，听说一般公司算法也就考考冒泡和快速。我听说的哈，别喷我

快速排序
publicclass QuickSort {
publicvoid QuickSort(inta[], intp, intr) {
if (p < r) {
intq = Partition(a, p, r);
QuickSort(a, p, q - 1);// 对左半段进行排序
QuickSort(a, q + 1, r);// 对右半段进行排序
}
}
publicint Partition(inta[], intstart, intend) {
inti, j;
i = start;
j = end;
if ((a == null) || (a.length == 0))
return -1;
while (i < j) {
while (i < j && a[i] <= a[j]) {
//以数组start下标的数据为key，右侧扫描
j--;
}
if (i < j) {
//右侧扫描，找出第一个比key小的，交换位置
inttemp = a[i];
a[i] = a[j];
a[j] = temp;
}
while (i < j && a[i] < a[j]) {
//左侧扫描（此时a[j]中存储着key值）
i++;
}
if (i < j) {
//找出第一个比key大的，交换位置
inttemp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
returnj;
}
publicstaticvoid main(String args[]) {
QuickSortq = new QuickSort();
int[] a = { 4, 3, 6, 1, 5, 2 };
q.QuickSort(a, 0, a.length - 1);
snp(a);
}
privatestaticvoid snp(int[] a) {
for (inti = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}

快速排序看这个理解 http://developer.51cto.com/art/201403/430986.htm

看看剑指Offer那本书