一、冒泡排序
这种排序方式是最容易理解的，主体思想就是：
指针重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
冒泡排序一次只比较两个数字，并且这两个数字是相邻的。
从图上我们可以看到，原数组为【30，8，15，18，12】。
第一次比较首先比较第0位和第一位，并且将结果大的数字往后移动，也就是交换。第0位是40， 第1 位是8，40>8，所以我们将大的数字往后移动。
同理，如果第0位<第1 位，我们就不进行交换。
之后我们在比较第1位和第2位的数字。将结果大的往后移动。
就这样，通过n-1次比较后（n为数组长度），我们就将最大的数字移到了数组的最末端。
然后再继续进行第二轮比较，找出第二大的数字，往后以此类推。
一共需要比较的次数为： (n-1)+(n-2)+(n-3)+·····+1；
以java代码方式实现：
public void bubblesort(int arrayVal[],int length) {
int i, j;
int temp;
for (i =0; i < length -1; i++) {
for (j = i +1; j < length; j++) {
if (arrayVal[i] > arrayVal[j]) {
//置换位置
temp = arrayVal[i];
arrayVal[i] = arrayVal[j];
arrayVal[j] = temp;
}
}
}
}
二、选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序就是对数组中的元素进行比较选择，然后直接放置在排序后的位置。
首先指针K先指向数组0号位置，K相当于指明一个目标位置。然后另一个指针min从K开始，往后一次比较，找到最小的值，并存储在min中，比较了一轮后，min中存储的数就是整个数组中最小的数字。这是直接将min中的数字和K指向的数字交换即可。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。
JAVA代码实现：
public void selectionsort(int arrayVal[],int length) {
int i, j, max;
int temp;
for (j = length; j >1; j--) {
max =0;//标记最值位置
for (i =1; i < j; i++) {
if (arrayVal[i] > arrayVal[max]) {
max = i;
if (max != j -1) {
temp = arrayVal[max];
arrayVal[max] = arrayVal[j -1];
arrayVal[j -1] = temp;
}
}
}
}
}
三、插入排序
要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
例如,已知待排序的一组记录是：
1，3，5，8，2，1
加入之前的1，3，5，8已经按照直接插入排序排序好了，现在我们需要对2进行排序。 首先将2存在一个临时变量temp中， 然后指针从2的前一位开始判断，如果前一位比2大，则将前一位往后移，以此类推，直到找到比2小的元素。这时将2插入进去。
JAVA代码实现:
public static void StraightInsertSort(int[] a) {
int temp =0,j =0;
for(int i =1;i < a.length;i++){
temp = a[i]; j = i;
while(j >0 && a[j-1] >= temp){
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
四、 二分插入排序
将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。所谓折半比较，就是在插入A[i]时，取A[i-1/2]的关键码值与A[i]的关键码值进行比较，如果A[i]的关键码值小于A[i-1/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，故可以在A[0]到A[i-1/2-1]之间继续使用折半比较；否则只能插入A[i-1/2]到A[i-1]之间，故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半，其中间结点为A[k+r/2]，经过一次比较即可排除一半记录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是文件记录必须按顺序存储。
JAVA代码实现：
public int getIndex(int arr[],int x){
int start=0;
int end=arr.length-1;
int min=0;
while(start<=end){
min=(start+end)/2;
if(x==arr[min]){
return min;
}else if(x
end=min-1;
}else if(x>arr[min){
start=min+1;
}
}
return -1;
}
网友评论