package algorithm.sort;
import java.util.Random;
public class Sort {
private static Random rand = new Random();
public void BubbleSort(int[] a, int length) {
for (int i = 0; i < length; i++)
for (int j = i + 1; j < length; j++) {
if (a[i] >= a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
public void InsertSort(int [] a,int length){
int temp,j;
for(int i=0;i<length;i++){
temp = a[i];
j = i-1;
while(j>=0&&temp<a[j]){
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
public void BinSort(int[] t, int length) {
int key, i, j, low, high, mid;
for (i = 1; i < length; i++) {
low = 0;
high = i - 1;
key = t[i];
while (low <= high) {
mid = (low + high) / 2;
if (key < t[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (j = i; j > high + 1; j--) {
t[j] = t[j - 1];
}
t[high + 1] = key;
}
}
private void MAX_HEAPIFY(int[] a, int i, int heapSize) {
int left = i * 2;
int right = i * 2 + 1;
int largest;
if (left <= heapSize && a[left] > a[i]) {
largest = left;
} else {
largest = i;
}
if (right <= heapSize && a[right] > a[largest]) {
largest = right;
}
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
MAX_HEAPIFY(a, largest, heapSize);
}
}
private void BUILD_MAX_HEAP(int[] a, int heapSize) {
for (int i = a.length / 2; i >= 0; i--) {
MAX_HEAPIFY(a, i, heapSize);
}
}
public void HeapSort(int[] a) {
BUILD_MAX_HEAP(a, a.length - 1);
int heapSize = a.length - 1;
for (int i = a.length - 1; i >= 1; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapSize = heapSize - 1;
MAX_HEAPIFY(a, 0, heapSize);
}
}
public void QuickSort(int[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
QuickSort(a, p, q - 1);
QuickSort(a, q + 1, r);
}
}
private int partition(int[] a, int p, int r) {
int i = p + rand.nextInt(r - p + 1);
swap(a,p,i);
int pivot = a[p];
int low = p;
int high = r;
while(low<high){
while(low<high&&a[high]>pivot){
high--;
}
if(low<high){
a[low]=a[high];
low++;
}
while(low<high&&a[low]<pivot){
low++;
}
if(low<high){
a[high]=a[low];
high--;
}
}
a[low] = pivot;
return low;
}
private static void swap(int x[],int a,int b){
int temp = x[a];
x[a] = x[b];
x[b] = temp;
}
public void mergeSort(int[] a,int[] temp,int low,int high){
if(low < high){
int mid = (low+high)/2;
mergeSort(a,temp,low,mid);
mergeSort(a,temp,mid+1,high);
merge(a,temp,low,mid,high);
}
}
private void merge(int[] a,int[] temp,int low,int mid,int high){
for(int i=low;i<=high;i++){
temp[i] = a[i];
}
int i=low,j=mid+1,k=low;
while((i<=low)&&(j<=high)){
if(temp[i]<=temp[j]){
a[k++] = temp[i++];
}else{
a[k++] = temp[j++];
}
}
while(i<=mid){
a[k++] = temp[i++];
}
while(j<=high){
a[k++] = temp[j++];
}
}
public static void main(String[] args) {
Sort sort = new Sort();
int a[] = { 7, 4, 3, 8, 9, 65, 23, 99, 15, 2, 0, 47 };
int temp[] = new int[a.length];
// sort.BubbleSort(a, a.length);
sort.InsertSort(a, a.length);
//sort.BinSort(a, a.length);
//sort.QuickSort(a,0,a.length-1);
// sort.HeapSort(a);
//sort.mergeSort(a, temp,0, a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
分享到:
相关推荐
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
数据结构复习.zip 各种排序算法、大二上算法合集
、第七章图、图的存储结构:、图的遍历、深度优先遍历(DFS)、广度优先遍历(BFS算法)、最小生成树、普里姆算法、克鲁斯卡尔算法、最短路径、迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法、拓扑排序、关键路径、第八...
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
数据结构与算法 数据结构与C语言 data structure课程 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 data structure课程 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 data structure...
算法-数据结构之【排序】复习题.rar
数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...
数据结构与算法 数据结构与C语言 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与...
数据结构与算法 数据结构与C语言 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与...
内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...
数据结构与算法 数据结构与C语言 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与...
数据结构与算法(Python) 一、引入概念 1-01算法引入 1-02 时间复杂度与大O表示法 1-03-最坏时间复杂度与计算规则 1-04-常见时间复杂度与大小关系 1-05-代码执行时间测量模块 1-06-Python列表类型不同操作的...
数据结构重要算法(含排序、查找)。 摘自《数据结构》这本书。 可以做小条哦。
数据结构的全面复习资料,重点难点; 二叉树 排序 查找、顺序表, 带有代码和相关的算法。
数据结构复习资料,较全面系统。包含堆栈,队列,树,图,等数据机构排序搜索等算法
Mark Allerl Weiss教授撰写的数据结构与算法分析方面的著作曾被评为20世纪最佳的30部计算机著作之一,已经成为公认的经典之作,被全球数百所大学采用为教材,广受好评。 本书秉承Weiss著作一贯的严谨风格,同时又...
清华大学 工程硕士 数据结构复习题.doc清华大学 工程硕士 数据结构复习题.doc清华大学 工程硕士 数据结构复习题.doc
设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为________ 模式匹配 数据结构期末复习习题全文共60页,当前为第6页。 6. 对二叉排序树进行_______遍历,可以得到按关键字从小到大排列的节点序列 ...
排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...