package com;
public class Sort {
private static int[] list = {7,3,4,1,9,2,8,5,6,0,5};
/**
* 冒泡排序, O(n^2)
*/
private static void bubble(){
for (int i = 0; i< list.length ; i++){
for (int j= 0; j< list.length -i -1; j++){
if (list[j] > list[j+1]){
int tmp = list[j];
list[j] = list[j+1];
list[j+1] = tmp;
}
}
}
}
/**
* 简单选择排序, O(n^2)
* 将要排序的对象分成两部分,一部分是已排序的,一部分是未排序的,从未排序的部分选择最小的,并放入已排序部分的最后一个
*/
private static void selection(){
for (int i = 0; i< list.length; i++){
int position = i;
for (int j =i + 1; j< list.length; j++){
if (list[position] > list[j]){
position = j;
}
}
int tmp = list[i];
list[i] = list[position];
list[position] = tmp;
}
}
/**
* 直接插入排序, O(n^2)
* 将数据分为两部分,从后面部分依次取出数据,插入前面部分(插入后的前面这部分有序)
*/
private static void insertion(){
for (int i=1; i<list.length; i++){
int j = i -1 ;
int tmp = list[i];
while(list[j] > tmp){
list[j+1] = list[j];
j--;
if (j<0) break;
}
list [j+1] = tmp ;
}
}
/**
* 快速排序, O(n*log n)
* 属于一种优化冒泡排序
* 定义一个枢轴,使得在其之前的都小于它之后的都大于等于它,然后按这个法则在枢轴两边递归运算;枢轴一般取第一个元素
*/
private static void quickSort(int low, int high){
if (low < high){
int p = partition(low,high);
quickSort(low, p-1);
quickSort(p+1, high);
}
}
/**
* 将序列划分为2个子序列,并返回枢轴元素位置;其中,枢轴元素前的元素都小于枢轴元素,后的都大于枢轴元素
*/
private static int partition(int low, int high){
int pivot = list[low];
while(low < high){
while(low < high && list[high] >= pivot) high --;
list[low] = list[high];
while(low < high && list[low] <= pivot) low ++;
list[high] = list[low];
}
list[low] = pivot;
return low;
}
/**
* 希尔排序,又称“缩小增量排序”,是改进的直接插入排序方式
* 时间复杂度依赖于步长序列,如当步长序列为delta[k]=2^(t-k+1) - 1,时间复杂度O(n^1.5)
* 本例,我们选择步长序列为:{5,3,1}
*/
private static void shell(){
int[] step = {5,3,1};
for (int i:step)
shellInsert(i);
}
private static void shellInsert(int deltaK){
for (int i=deltaK; i<list.length; i++){
if (list[i]<list[i-deltaK]){
int tmp = list[i];
int j = i - deltaK;
for (;j>=0 && tmp < list[j]; j-=deltaK ){
list[j + deltaK] = list[j];
}
list[j+deltaK] = tmp ;
}
}
}
public static void main(String[] args) {
bubble();
// selection();
// insertion();
// quickSort(0, list.length -1);
// shell();
for (int x:list)
System.out.print(x+" ");
}
}
分享到:
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...