数据结构几种排序代码
2017-06-05 20:41:58 hqweay 阅读数 315

第一种 直接插入排序

简单地考虑比较数字大小,而不考虑排序其他数据类型。

如果考虑排序其他类型的数据,其实也就是排序这种类型的关键字key来排序。

#include<stdio.h>
int main(){
	int a[5];
	for(int i = 0; i < 5; i++){
		
		scanf("%d", &a[i]);
	}
	
	int i,j;
	int temp;
	for(i = 1; i < 5; i++){
		if(a[i] < a[i-1]){
			temp = a[i];
			for(j = i - 1; j >=0 && a[j] > temp; j--){
				a[j+1] = a[j];	
			}
			a[j+1] = temp;
		}
	}
	
	for(int i = 0; i < 5; i++){
		
		printf("%d", a[i]);
	}
}

2014-06-07 22:50:05 wangdianyong 阅读数 814

自己以前学的是C++版的数据结构后来学java对于数据结构中的排序虽然熟悉但是都已经忘了

所以今天就重新用java写了,如有不足之处,还望不吝赐教!

先从简单的开始吧


直接插入排序

主要思想:每次与前一个关键字比较大的值向后移一位。

package com.iss.demo;


public class InsertSort {

/**
* 直接插入比较的基本原理每次与前一个比较大的向后移
* @param args
*/


// 直接插入排序
public static void main(String[] args) {
int[] a = { 2, 1, 4, 2, 7, 8, 6 };
System.out.println("排序前:");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");


}


// 每次与前一个进行比较,若前面一个比较若比自己大就像后移一位
for (int i = 1; i < a.length; i++) {
int j;
int temp = a[i];
for (j = i - 1; j >= 0; j--) {
if (a[j] > temp) {
a[j + 1] = a[j];// 如果a[j]>temp向后移一位
} else {
break;
}


}
a[j + 1] = temp;//不是a[j] 原因是循环后j--


}
System.out.println();
System.out.println("排序后:");


for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");


}


}


}



选择排序


主要思想:一趟排序中选出最小的赋给数组的第一个值。

public class SelectionSort {

// 选择排序每次比较取出最小值给一个下标
public static void selectionSort(int[] a) {

int min = 0;

int temp;
for (int i = 0; i < a.length; i++) {
min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
temp = a[min];
a[min] = a[i];
a[i] = temp;


}


}


public static void main(String[] args) {


int[] a = { 2, 1, 4, 5, 9, 8, 7 };


selectionSort(a);


for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");

}
}

}

最经典冒泡排序

主要思想:每一趟两两比较取最大值一共比较n-1-i次。

public class BubbleSort {


public void bubbleSort(int[] arr) {


// 冒泡排序基本原理比较取最大值 每一趟需要比较n-1-i次
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}


}

        public static void main(String[] args) {
int[] arr = { 2, 1, 3, 4, 6, 5 };
// new BubbleSort().bubbleSort(arr);
// new BubbleSort().SelectionSort(arr);


new BubbleSort().bubbleSort1(arr);


for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);


}


}


}

最不容易的理解的快速排序

主要思想:

通过一趟排序将排序记录分割成独立的两部分,其中一部分记录的关键字比另一部分的关键字小,

然后对这两部分再进行排序直到,整个序列有序。

算法思想:把整个序列看做一个数组,把第零个位置和最后一个比较,如果比它小交换,否则不

做处理;交换以后再和小的那端比。比他小不交换,比他大交换。这样循环往复,一趟排序完成,

左边就是比中轴小的,右边就是比中轴大的,然后再用分治法,分别对独立的数组进行排序。

package com.iss.sort;


public class QuickSort {


public int getMiddle(int[] a, int low, int high) {


int temp = a[low];


while (low < high) {
while (low < high && temp <= a[high]) {
high--;
}// 若不加等于会死循环


a[low] = a[high];


while (low < high && temp >= a[low]) {
low++;
}


a[high] = a[low];
}


a[low] = temp;// 中轴记录到尾


return low;
}


public void quickSort(int[] a, int low, int high) {
if (low < high) {
int middle = this.getMiddle(a, low, high);


quickSort(a, low, middle - 1);
quickSort(a, middle + 1, high);


}
}


// public void quick_sort(int[] a) {
// if (a.length > 0) {
// this.quickSort(a, 0, a.length - 1);
// }
// }


public static void main(String[] args) {
int[] a = { 2, 1, 4, 2, 6, 8, 90, 4, 5 };


new QuickSort().quickSort(a, 0, a.length - 1);


for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");


}
}


}

附赠另一种方式的快速排序

package com.iss.sort;


public class QuickSort1 {


public void quickSort(int[] a, int left, int right) {
int i, j, middle, temp;


i = left;
j = right;
middle = (i + j) / 2;


while (i < j) {
while (a[i] < a[middle] && i < right) {
i++;
}// 不能是等于是等于中间的值不变了就无法成功排序
while (a[j] > a[middle] && j > left) {
j--;
}


if (i <= j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}


if (i < right) {
this.quickSort(a, i, right);
}
if (j > left) {
this.quickSort(a, left, j);
}


}


public static void main(String[] args) {


int[] a = { 2, 2, 1, 4, 67, 3, 7, 8, 9 };


new QuickSort1().quickSort(a, 0, a.length - 1);


for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");


}
}


}


几种排序的时间复杂度

选择排序算法时间复杂度是O(n^2)

插入排序算法时间复杂度是O(n^2)

冒泡排序算法时间复杂度是O(n^2)

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n),最坏O(n^2)。


另有几种排序原谅笔者还不精通!后续有时间再更!







2015-05-31 18:03:08 wzq6578702 阅读数 400

(一)常见排序


import java.util.Arrays;

public class Sort {
//快速排序
	private static int partition(int[] arr, int low, int hight) {
		int pivotkey = arr[low];
		while (low < hight) {
			while (low < hight && pivotkey <= arr[hight])
				--hight;
			int temp1 = arr[low];
			arr[low]=arr[hight];
			arr[hight]=temp1;
			//arr[low] = arr[hight];
			while (low < hight && pivotkey >= arr[low])
				++low;
			int temp2 = arr[low];
			arr[low]=arr[hight];
			arr[hight]=temp2;
			//arr[hight] = arr[low];
		}
		return low;
	}
//快速排序
	public static void qSort(int[] arr, int low, int hight) {
		if (low < hight) {
			int pivotkey = partition(arr, low, hight);
			qSort(arr, low, pivotkey - 1);
			qSort(arr, pivotkey + 1, hight);
		}
	}
//插入排序
	public static int[] insertOrder(int a[]){
		for (int i = 1; i < a.length; i++) {
			int k = a[i];
			int j;
			for (j = i - 1; j >= 0 && k < a[j]; j--) {
				a[j + 1] = a[j];
			}
			a[j + 1] = k;
			//System.out.println(Arrays.toString(a));
		}
		return a;
	}
	//冒泡排序
	public static int[] maopao(int[] a){
		
		for(int i=0;i<a.length-1;i++){//i 代表伦次
			for(int j=0;j<a.length-i-1;j++){//j和j+1代表相邻元素
				if(a[j]>a[j+1]){
					int temp = a[j];
					a[j]= a[j+1];
					a[j+1]=temp;
				}
			}
			//System.out.println(Arrays.toString(a));
			//Arrays.sort(a);
		}
		return a;
	}
	//选择排序
	public int[] selectOrder(int arr[] ) {
		for (int i = 0; i <arr.length; i++) {
			int max = arr[i];
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < max) {
					int temp = arr[j];
					arr[j] = max;
					max = temp;
					arr[i] = max;
				}
			}
		}
		return arr;
	}
	
	// 二分查找
		public void binarySearch() {
			int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
			int start = 0;
			int end = b.length - 1;
			int mid;
			int target = 1;
			while (true) {
				mid = ((end + start) / 2);
				if (b[mid] == target) {
					System.out.println(mid);
					break;
				}
				if (target < b[mid]) {
					end = mid;
				}
				if (target > b[mid]) {
					start = mid + 1;
				}

			}
		}
	
	public static void main(String args[]) {
		int Arr[] = { 10, 30, 20, 50, 90, 80, 60, 40, 70 };
		System.out.println(Arrays.toString(Arr));
		qSort(Arr, 0, Arr.length -1);
		System.out.println(Arrays.toString(Arr));
	}
}
希尔排序:
算法思想

它是对插入插入排序的改进

搜索维基百科可知 
希尔排序,也称递减增量排序算法
假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ] 
,我们分别以步长为5,3,1进行排序(希尔排序最后的步长一定是1)

步长为5,我们可以得到如下数据, 
13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10
然后 按照列排序 
10 14 73 25 23 
13 27 94 33 39 
25 59 94 65 82 
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序: 
10 14 13 
25 23 33 
27 25 59 
39 65 73 
45 94 82 
94 
-最后以1步长进行排序(此时就是简单的插入排序了)。

public static void shellPass(Integer[] array, int d) {
    for (int i = d; i < array.length; i++) {
        int temp = array[i];
        int j = i - d;
        while (j >= 0 && array[j] > temp) {
            array[j + d] = array[j];
            j -= d;
        }
        array[j + d] = temp;
    }
}

public static void shellSort(Integer[] data) {
    int increment = 12;
    do {
        increment = increment / 3 + 1;
        shellPass(data, increment);
    } while (increment > 1);

}

(二)常见数据结构
2.1 graph
2.1.1图节点

public class GraphNode {
	int val;
    GraphNode next;
    GraphNode[] neighbors;
    boolean visited;
 
    GraphNode(int x) {
        val = x;
    }
 
    GraphNode(int x, GraphNode[] n){
        val = x;
        neighbors = n;
    }
 
    public String toString(){
        return "value: "+ this.val; 
    }
}

2.1.2队列


public class Queue {
	 GraphNode first, last;
	 
	    public void enqueue(GraphNode n){
	        if(first == null){
	            first = n;
	            last = first;
	        }else{
	            last.next = n;
	            last = n;
	        }
	    }
	 
	    public GraphNode dequeue(){
	        if(first == null){
	            return null;
	        }else{
	            GraphNode temp = new GraphNode(first.val, first.neighbors);
	            first = first.next;
	            return temp;
	        }   
	    }
}

2.1.3测试类

public class GraphTest {
    public static void main(String[] args) {
        GraphNode n1 = new GraphNode(1); 
        GraphNode n2 = new GraphNode(2); 
        GraphNode n3 = new GraphNode(3); 
        GraphNode n4 = new GraphNode(4); 
        GraphNode n5 = new GraphNode(5); 
 
        n1.neighbors = new GraphNode[]{n2,n3,n5};
        n2.neighbors = new GraphNode[]{n1,n4};
        n3.neighbors = new GraphNode[]{n1,n4,n5};
        n4.neighbors = new GraphNode[]{n2,n3,n5};
        n5.neighbors = new GraphNode[]{n1,n3,n4};
 
        breathFirstSearch(n1, 5);
    }
 
    public static void breathFirstSearch(GraphNode root, int x){
        if(root.val == x)
            System.out.println("find in root");
 
        Queue queue = new Queue();
        root.visited = true;
        queue.enqueue(root);
 
        while(queue.first != null){
            GraphNode c = (GraphNode) queue.dequeue();
            for(GraphNode n: c.neighbors){
 
                if(!n.visited){
                    System.out.print(n + " ");
                    n.visited = true;
                    if(n.val == x)
                        System.out.println("Find "+n);
                    queue.enqueue(n);
                }
            }
        }
    }
}

2.2link
2.2.1链表实例节点

public class Node {
    int val;
    Node next;
  
    Node(int x) {
        val = x;
        next = null;
}
}

2.3Queue
2.3.1队列节点

public class Node {
    int val;
    Node next;
  
    Node(int x) {
        val = x;
        next = null;
}
}

2.3.2队列操作类


public class Queue {
	Node first, last;
	 
    public void enqueue(Node n){
        if(first == null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
 
    public Node dequeue(){
        if(first == null){
            return null;
        }else{
            Node temp = new Node(first.val);
            first = first.next;
            return temp;
        }   
    }
}

2.4stack
2.4.1栈的节点

public class Node {
    int val;
    Node next;
  
    Node(int x) {
        val = x;
        next = null;
}
}

2.4.2栈的操作类


public class Stack {
	Node top; 
	 
    public Node peek(){
        if(top != null){
            return top;
        }
 
        return null;
    }
 
    public Node pop(){
        if(top == null){
            return null;
        }else{
            Node temp = new Node(top.val);
            top = top.next;
            return temp;    
        }
    }
 
    public void push(Node n){
        if(n != null){
            n.next = top;
            top = n;
        }
    }
}

2.5Tree
2.5.1数的节点

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

2015-06-28 11:19:40 cc4167 阅读数 32
最新整理书籍,无意间翻出大学时期数据结构课本,随便翻阅了其中关于排序这一章,粗略的看了下突然觉得比较陌生,作为计算机基础的东西,自己工作了反而用的比较少,平时自己也没有太关注,为了以后万一需要找工作方便复习这些东西,今写于此。

快速排序:快速排序是对冒泡排序的一种改进,冒泡排序是比较的相邻两个元素,故比较的次数以及元素移动的频率比较大。快速排序有效的改进了这一不足,比较的元素位置相隔比较远,并且是由两端向中间比较。
下面基于java语言实现快速排序算法。

	private static int quickSort(int low, int high , int a[] ) {
int tmp = a[low]; //一般选取数组第一个元素为比较的元素
while (low < high) {
//从数组的右边也就是数组末尾向前开始比较,小的放在数组前段,大的放置于后段
//当后段元素比tmp大,则不需移动直接进行下一个元素比较
while ((low < high) && a[high] > tmp) {
high--;
}

//当遇到后段元素比tmp小直接把后端元素交换至迁low位置
a[low] = a[high];

//tmp交换至后端之后,开始和前段元素进行比较
while (low < high && a[low] < tmp) {
low++;
}

//交换前端元素到后端
a[high] = a[low];
}
//这是第一趟排序完成,tmp此时至于数组个元素大小的最中间
a[low] = tmp;
//返回中间位置即数组中间位置的下标
//到此时整个数组的排序并未完成,完成的只是一趟,后续的排序原理相同,只是比较的数组起始位置下标不同,故可以采用递归算法实现。
return low;
}


	private static void quick(int low, int high , int a[] ) {
if (a.length > 0 && low < high){
int middle = quickSort(low, high, a);
quick(low, middle - 1, a);
quick(middle + 1, high, a);
}



插入排序:

	public void insertSort1(int a[]) {
int j; // 当前值的位置
int i; // 指向j前的位置
int key; // 当前要进行插入排序的值
// 从数组的第二个位置开始遍历值
for (j = 1; j < a.length; j++) {
key = a[j];
i = j - 1;
// a[i]比当前值大时,a[i]后移一位,空出i的位置,好让下一次循环的值后移
while (i >= 0 && a[i] > key) {
a[i + 1] = a[i]; // 将a[i]值后移
i--; // i前移
}// 跳出循环(找到要插入的中间位置或已遍历到0下标)
a[i + 1] = key; // 将当前值插入

for (int n = 0; n < a.length; n++) {
System.out.print(a[n] + " ");
}
System.out.println("\n");
}
}
2017-10-21 22:26:39 GXing007 阅读数 1021

数据结构之冒泡排序:(是一种稳定排序)

function maopao(arr){

    for(var i=0;i<arr.length-1;i++){
        for(var j=0;j<arr.length-1-i;j++)
            if(arr[j]>arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
}
}
}
    return arr;
}
var arr=[3,1,6,4,0];
maopao(arr);

console.log(arr);


冒泡排序最理想情况下:时间复杂度为O(n);

冒泡排序最理想情况下:时间复杂度为O(n^2);

 

数据结构之选择排序:

function xuanze(arr){
    for(var i=0;i<arr.length;i++){
        var min=arr[i];
                var index=i;
        for(var j=i+1;j<arr.length;j++){
            if(arr[j]<min){
                min=arr[j];
                index=j;
    
}
                
}
                var tem=arr[i];
                arr[i]=arr[index];
                arr[index]=tem;
}

    return arr;
};


var arr=[17,4,9,10,4,8];
xuanze(arr);
console.log(arr);

选择排序:时间复杂度为O(n^2)
 

 

数据结构之七大排序(代码)

阅读数 231

数据结构之排序今天晚上复习数据结构的排序算法,花了一晚上手撸了七种排序算法:冒泡、选择、插入、shell、堆排序、归并排序、快速排序……现在已然是深夜十一点多,就姑且发个博客,贴上我所写的代码。对于每种排序的原理,由于实在想睡觉了,就不进行深入阐述,一切都在代码中。注意:本人代码都经过对数器验证,可以保证正确性~1、冒泡排序/* …………冒泡排序…………  ...

博文 来自: qq_38180223

数据结构-排序进阶代码

阅读数 640

数据结构-排序进阶代码

博文 来自: qq78442761

数据结构--Java实现几种常见排序

阅读数 740

第一次在CSDN上写博客,今天晚上刚好复习了一下排序相关的东西,就写一写这个吧。(话说markdown还不熟悉。。)冒泡排序:复杂度o(n^2)可以增加一个flag标记减少比较趟数稳定publicstaticvoidbubbleSort(int[]arr){//时间复杂度:O(n*2)intcount=0;for(inti=

博文 来自: sinat_33516485

Python数据结构与算法(几种排序)

阅读数 22

转发:http://www.cnblogs.com/fwl8888/p/9315730.html转发一篇博客,关于几种排序算法讲的非常清楚,一看就懂的那种,收藏~

博文 来自: sinat_34246179

数据结构中几种排序的java实现

阅读数 77

1.选择排序“`publicstaticint[]selectSort(int[]arrys){inthigh=arrys.length;for(inti=0;i**2.冒泡排序**publicstaticint[]bubbleSort(int[]arrys){for(inti=0;i&amp;amp;amp;lt;arr...

博文 来自: ocean_java666
没有更多推荐了,返回首页