`

数据结构之常用排序算法理解

阅读更多

1.选择排序:

遍历数组,每一次遍历找出一个最小值放在数组前面,步骤如下:

  1. 将currMin设为a[0],遍历a[1]->a[n-1],只要a[i]小于a[0],进行a[0]与a[i]的交换
  2. 将currMin设为a[1],遍历a[2]->a[n-1]
  3. 最后一个currMin为a[n-2],比较a[n-2]与a[n-1]

代码如下:

 

for(int i=0; i<arr.length -1; i++) {
    int currMin = arr[i];
    int currMinIndex = i;
    for (int j=i+1; j<arr.length; j++) {
        if(currMin > arr[j]) {
            currMin = arr[j];
            currMinIndex = j;
        }
    }
    if(currMinIndex != i) {
        list[currMinIndex] = a[i];
        a[i] = currMin;
    }
}

 

2.插入排序:

这个算法可以描述为: 将a[i]插入到已排号序的子数列中,然后a[0]->a[i]就是有序的

for(int i=1; i<arr.length; i++) {
    int currEle = arr[i];
    for (int j =i-1; j>=0&&arr[j]>currEle; j--){
        arr[j+1] = arr[j]
    }
    arr[j+1] = currEle

}

 

3.冒泡排序

遍历数组,每一次遍历后将值最大的元素交换到数组尾部,关键代码如下:

for(int out=1; out<a.lenght; out++){
    for (int in=0; in<a.length-out; in++)
        if(a[i] > a[i+1]){
            int temp = a[i];
            a[i] = a[i+1]
            a[i+1] = temp;
        }
        
}

 

4.归并排序

归并排序通过递归实现,思想非常容易理解:

public static void mergeSort(int[] list){
		if (list.length <1) {
			mergeSort(list[0->list.length/2]);
			mergeSort(list[list.length/2+1 ->list.length]);
			merge(int[firstHalfList], int[secondHalfList]);			
		}
	}
	
	public static int[] merge(int[] first, int[] second){
		int index1=0,index2=0,index3=0;
		int[] result;
		//将两个数组中的数据按大小先后存储到result中
		while(index1<first.length && index2<second.length){
			if(first[index1]<second(index2)){
				result[index3] =first[index1];
				++index1;
				++index3
			} else {
				result[index3] =second[index2];
				++index2;
				++index3
			}
			
		}
		//将剩下最大的数据,单独再追加到result表
		while (index1 <first.length) {
			result[index3++] = first[index1++];
		}
		while (index2 < second.length) {
			result[index3++] = first[index2++];
		}
	}

 

5.快速排序

快速排序跟归并排序一样采用的递归的方法实现:

public static void quickSort(int[] list){
		quickSort(list, 0, list.length-1);
		
	}
	
	public static void quickSort(int list[], int first, int last){
		if (last>first){
			int pindex = partition(list, first, last);
			quickSort(list, first, pindex-1);
			quickSort(list, pindex, last);
			
		}
	} 
  • 快速排序关键是pindex的计算,在计算pindex的时候, list[0, pindex-1]的元素都比a[pindex]小,list[pindex+1, length-1]中的元素都比a[pindex]大
  • 在进行partition的时候,数组中元素进行交换

 

0
1
分享到:
评论
1 楼 留下的祝福 2013-10-29  

快速排序和冒泡排序属于选择排序这一大类!

相关推荐

    用JavaScript实现的常用排序算法和数据结构的交互式概述

    常用排序算法和数据结构的交互式概述,用JavaScript实现。 还包括其他几个其他的算法挑战,类似于在编程访谈中提出的问题。 这是为了帮助您在准备面试时更好地理解计算机科学的基础知识,算法和解决问题的能力。

    数据结构、机器学习、常用算法、经典案例、排序、加密算法.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    数据结构与常用算法的学习、刷题.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    基于C语言数据结构二叉树建立遍历冒泡排序快速排序等的毕业设计,二叉树不仅是一种数据结构,而且还是许多算法的基础

    冒泡排序和快速排序是两种常用的排序算法,它们的实现依赖于对数据的遍历。因此,本毕设旨在通过二叉树的遍历来实现这两种排序算法的实现。 ## 二、研究内容 本毕设将包括以下内容: 1. 二叉树的建立和遍历:包括...

    常用算法与数据结构.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    常用数据结构和算法总结.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    Java实现常用数据结构和算法.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    北大数据结构代码

    熟练掌握插入排序、Shell排序、堆排序、快速排序、基数排序等常用的各种排序算法及其时间和空间开销。 6. 了解文件管理(数据在外存中的组织形式)和外排序技术。 7. 了解检索和索引技术。 8. 掌握自组织...

    Python数据结构算法讲解(数据结构+算法+面试指南)

    本资源是一套全面的Python数据结构和算法学习材料,旨在帮助读者从基础到高级逐步掌握Python中的数据结构与算法。通过本资源,读者不仅能学习到数据结构的基本原理和算法的实现技巧,还能了解如何在技术面试中有效地...

    Data Structure and Algorithms(常用数据结构与算法).zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    常用设计模式、数据结构、算法等的demo.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    常用的数据结构,算法,设计模式的积累。.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    一些常用的数据结构和算法的实现.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    数据结构案例教程(C语言版).rar

    《数据结构案例教程(C语言版)》对给出的每一种算法,均先描述了它的基本思路和要点,使得算法清晰易读,便于学生理解和掌握。《数据结构案例教程(C语言版)》共分为8章,内容包括线性表,栈和队列,串、数组和广义表...

    数据结构与算法程序示例。常用算法思想总结归档。使知识体系化.zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    深度解构编程常用算法、数据结构,使其不再抽象、深奥(持续更新....).zip

    排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法,分支限界...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    他善于用容易理解的方法和语言说明复杂的概念。许多人认为他开创了计算机书籍贴近大众的新风,为我国的计算机普及事业做出了重要的贡献。 谭浩强教授曾获全国高校教学成果国家级奖、国家科技进步奖,以及北京市政府...

    数据结构(C语言)实验教程实验数据

    其目的在于帮助读者通过实验练习,深入理解各种常用数据结构的特性与应用方法,并通过配合合理的程序设计训练,提高读者的程序设计水平,培养良好的程序设计习惯。全书内容共分8章,安排了7个以C语言为工具的实验...

    《数据结构》习题答案

    第1章概述,主要介绍数据、数据结构和算法等基本概念。第2章至第6章分别讨论线性表、栈、队列、串、数组和广义表、树及图等基本类型的数据结构,内容包括它们的逻辑结构、存储结构以及在各种存储结构下相应运算的...

    数据结构实验五 快速、堆、基数排序算法的设计.doc

    2.掌握常用的排序方法,并掌握用高级语言实现排序算法的方法。 3.了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的性能的分析方法。 实验要求: 要求彻底弄懂排序的物理存储结构,并通过此试验为以后的...

Global site tag (gtag.js) - Google Analytics