由于最近要应付面试,所以把几个常见的排序方法有复习了一下。
一 插入排序
看见过一个很形象的比喻:
插入排序算法是一个对少量元素进行排序的有效算法。插入排序的工作原理与打牌时整理手中的牌的做法类似,开始摸牌时,我们的左手是空的,接着一次从桌上摸起一张牌,并将它插入到左手的正确位置。为了找到这张牌的正确位置,要将它与手中已有的牌从右到左进行比较,无论什么时候手中的牌都是排序好的。
原理:将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
/**
* i 前方的数据都是已经排序好的 当A[i]>A[i-1]时 直接放入其后面 否则就和i-1中的数据调换位置
* 时间复杂度:O(n^2)
* @param
*/
public static void sort(int[] A){
for(int i=1;i<A.length;i++){
int j=i;
while(A[j]<A[j-1]){ // 要插入的数据比前一个小时 就调换位置
int temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
j--;
if(j==0)
break;
}
}
}
效率:
时间复杂度:O(n^2).
二 快速排序(转载)
详情:http://blog.csdn.net/morewindows/article/details/6684558
基本思路:
该方法的基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
代码
//快速排序
public static void quick_sort(int s[], int l, int r) {
if(l<r){
int low=l;
int high=r;
int temp=s[l];
while(low<high){
while(low<high&&s[high]>temp) // 从右向左找第一个小于x的数
high--;
s[low]=s[high];
while(low<high&&s[low]<temp) // 从左向右找第一个大于等于x的数
low++;
s[high]=s[low];
}
s[low]=temp;
quick_sort(s, l,low-1);
quick_sort(s, low+1, r);
}
}
三 选择排序
原理:
从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作了。
代码:
public static void quick_sort(int[] A) {
for (int i = 0; i < A.length; i++) {
int index = i;
for (int j = i + 1; j < A.length; j++) {
// 遍历i之后的数据,找到其中最小值
if (A[j] < A[index])
index = j;
}
// 将最小值所在位置与i交换
if (i != index) {
int temp = A[i];
A[i] = A[index];
A[index] = temp;
}
}
}
四 冒泡排序
原理
是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
这样一趟过去后,最大或最小的数字被交换到了最后一位,
代码:
public static void quick_sort(int[] A) {
for(int i=0;i<A.length;i++){
for(int j=i+1;j<A.length;j++){
if(A[j]<A[i]){
//交换位置
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
}
}
分享到:
相关推荐
提供了Java实现几种常见排序方法和原理介绍
常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大...点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用UNICODE。
C++ 常见的几种排序: 冒泡排序 插入排序 快速排序 选择排序
此程序是数据结构中的几种常见的排序方法,包括选择插入等常见排序
几种常见的排序方法 1. 选择排序法基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 2.插入排序(Insertion Sort)的基本思想是...
最常见的几种排序算法 网页形式的,忘记什么时候找的了
Java中几种比较常见的排序方法,像冒泡、快速排序、插入排序登。
用Java实现几种常见的排序算法.txt
java排序算法,包括冒泡、插入、快速、选择等四种最常见的排序算法
几种常见的排序算法代码,附有其效率及分析
数据结构中几种常见的排序算法之比较,比较常见的冒泡排序、快速排序等
包括常见的几种排序:快速排序,归并排序,冒泡排序,希尔排序,堆排序
涵盖了数组的冒泡、选择、插入等常见排序方法,并有详细的注释,通俗易懂
这是几种常见的排序算法,我是用C语言编写的,而且代码都是经过我亲自认证的,保证没有什么问题!希望需要的宅男宅女们可以用到!
常见的几种排序算法源代码,很详细,很准确
常见的几种排序算法的实现,希尔排序,冒泡排序、、、
Java几种常见的排序算法
这是本人今天上传的最后一个文档了,是关于排序的,介绍了几种常用的排序方法,本人原创的
功能:实现各种排序算法:冒泡排序、选择排序、堆排序、插入排序、希尔排序、快速排序、二叉树排序、归并排序
几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...