插入排序
插入排序是一种通过不断地把新元素插入到已排好序的数据中的排序算法,常用的插入排序算法包括直接插入排序和shell排序,直接插入排序实现比较简单,时间复杂度是O(n),但是直接插入没有充分的利用已插入的数据已经排序这个事实,因此有很多针对直接插入排序改进的算法,例如折半插入排序等,下边是直接插入排序的Java实现:
public static void insertSort(int[] elements){
for(int i = 1;i <elements.length; i++){
int j = -1;
while(j <= i && elements[i] > elements[++j]);//找到element[i]应该摆放的位置,此处可以利用查找算法进行优化
if(j < i){
//将j之后的数据移动一位,然后把elements[i]移动到j处
int temp = elements[i];
for(int k = i-1;k >= j;k--){
elements[k+1] = elements[k];
}
elements[j] = temp;
}
}
}
另一种常用的插入排序算法:Shell排序也是对直接插入排序算法的一种优化,因此可以说直接插入排序是一种特殊的Shell排序,Shell排序对直接插入排序的优化主要体现在,Shell排序通过使用一个增量序列(递减),每次把要排序的数组分成几个子数组,然后对子数组进行插入排序,这样可以减少比较和移动数据的次数,Shell排序是一种非常高效的排序算法,该算法的思想是:
1.以h(h一般取n/2)为间隔将n个元素列分为几个小组,在每个小组内按直接插入法排序
2.令h=h/2,重复第1步
3.当h=1时,排序结束(此时相当于直接插入排序,不过由于数据已经基本排好序,因此比较次数和移动次数比直接插入排序少很多)
Shell排序的Java实现如下:
public static void shellSort(int[] elements){
for(int h = elements.length/2;h > 0;h /= 2){
for(int i = h;i < elements.length; i++){
int j = i % h;
while(j <= i && elements[i] > elements[j]) j += h;//找到element[i]应该摆放的位置
if(j < i){
//将j之后的数据移动h位,然后把elements[i]移动到j处
int temp = elements[i];
for(int k = i-h;k >= j;k -= h){
elements[k+h] = elements[k];
}
elements[j] = temp;
}
}
}
}
快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)。
package src;
public class QSort
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO 自动生成方法存根
quicksort qs = new quicksort();
int data[] = {44,22,2,32,54,22,88,77,99,11};
qs.data = data;
qs.sort(0, qs.data.length-1);
qs.display();
}
}
class quicksort
{
public int data[];
private int partition(int sortArray[],int low,int hight)
{
int key = sortArray[low];
while(low<hight)
{
while(low<hight && sortArray[hight]>=key)
hight--;
sortArray[low] = sortArray[hight];
while(low<hight && sortArray[low]<=key)
low++;
sortArray[hight] = sortArray[low];
}
sortArray[low] = key;
return low;
}
public void sort(int low,int hight)
{
if(low<hight)
{
int result = partition(data,low,hight);
sort(low,result-1);
sort(result+1,hight);
}
}
public void display()
{
for(int i=0;i<data.length;i++)
{
System.out.print(data[i]);
System.out.print(" ");
}
}
}
选择排序
public class ChooseSort {
private final long[] origArr = new long[] { 12, 65, 2, 33, 89, 23, 10 };
private final static int SORT_DEST = 0;
private final static int SORT_ASC = 1;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ChooseSort chooseSort = new ChooseSort();
chooseSort.sort(chooseSort.origArr, ChooseSort.SORT_ASC);
for (int j = 0; j < chooseSort.origArr.length; j++) {
System.out.println(chooseSort.origArr[j]);
}
}
public void sort(long[] arrays, int sortType) {
int len = this.origArr.length;
for (int i = 0; i < len; i++) {
// 从左往右比较
int destIndex = i;
for (int j = i; j < len - 1; j++) {
if (sortType == ChooseSort.SORT_DEST) {
if (this.origArr[destIndex] < this.origArr[j + 1]) {
// this.swap(i, j + 1);
destIndex = j + 1;
}
} else {
if (this.origArr[destIndex] > this.origArr[j + 1]) {
// this.swap(i, j + 1);
destIndex = j + 1;
}
}
}
this.swap(i, destIndex);
}
}
public void swap(int leftInde, int rightIndex) {
long temp = this.origArr[leftInde];
this.origArr[leftInde] = this.origArr[rightIndex];
this.origArr[rightIndex] = temp;
}
}
分享到:
相关推荐
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
排序算法汇总.pdf
各种排序算法汇总,包括插入排序、基数排序等
实现所有经典排序算法汇总。实现所有经典排序算法汇总。实现所有经典排序算法汇总。实现所有经典排序算法汇总。实现所有经典排序算法汇总。实现所有经典排序算法汇总。
java常用的7大排序算法汇总文档汇总
排序算法汇总P: 冒泡排序快速排序直接选择排序插入排序希尔排序 堆排序........
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
排序算法:排序算法汇总--各类排序算法 冒泡,选择,插入,快排,归并,堆排
7种排序算法程序汇总 冒泡排序 选择排序 插入排序 希排序尔 快速排序 二叉排序树 堆排序
JAVA排序算法汇总 常用的几种排序算法的JAVA实现,很有用的。
java排序算法汇总 将数据结构里的排序算法使用java实现 包括:归并 快速排序 直接选择 插入。。。。
排序算法汇总(选择排序 ,直接插入排序,冒泡排序,希尔排序,快速排序,堆排序)
8种经典排序算法汇总
交换排序 插入排序 选择排序 堆排序 归并排序 比较统计排序 分布统计排序
本人实现的排序算法,没有采用泛型,以后再改进
java 排序汇总 排序 算法 java 排序汇总 排序 算法
基于C++/C实现 7种面试管经常问到的排序算法
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 【基本要求】 (1)实现各种内部排序。包括冒泡排序,直接选择排序,希尔排序,快速排序,堆排序。 (2) 待排序的元素的关键字为整数...
数据结构各种排序算法汇总,c++语言编写!希望对大家有帮助