本次介绍排序算法中的插入排序。 1.直接插入排序:基本思想:直接插入排序也需要对待排序的序列在外层进行n-1次遍历,每次遍历时只把本次遍历次数处的元素和该元素之前的元素进行比较,来决定插入位置,并把从插入位置开始到该元素之前的所有元素后移,使从序列开始到该元素为止序列中的元素有序,直至遍历完成序列整体有序,插入排序算法的时间复杂度为O(n2);如下表格所示为待排序的序列:321765489当进行第一次遍历时把元素e[1]...
1/** 2 * 03/09/20143 * 4 * @author Burke5 *6*/ 7publicclass Sort {8 9publicstaticvoid main(String[] args) { 10int[] source = {4, 2, 1, 6, 3, 6, 0, -5, 1, 1}; 11 dichotomySort(source); 12for (int i = 0; i < source.length; i++) { 13 System.out.print(source[i] + " "); 14 } 15 } 1617/*18 * 二分排序:就是插入排序法的一种修改,当a[0],a[1]...a[i-1]排好序, 19 * 寻找第...
// test_max.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <cv.h> #include <highgui.h> #include <ml.h> #include <cxcore.h>#include <iostream> using namespace std;int main() {// step 1: //训练数据的分类标记,即4类float labels[16] = {1.0, 1.0,1.0,1.0,2.0,2.0,2.0,2.0,3.0,3.0,3.0,3.0,4.0,4.0,4.0,4.0}; CvMat labelsMat = cvMat(16, 1, CV_32FC1, labels); //训练数据矩阵float trainin...
package com.xsz.demo; /** * @author cwqi * @date 2015-1-6 *///排序之快速排序,基本思路為分治+挖坑,方法有兩種:一是雙邊掃面;二是單邊掃描。 public class QuickSort {public static void main (String[] args){int a[] ={2,3,30,1,4,56,2,7,3,8};//int a[] ={4,5,6,2,7,3,8};//int a[] ={1,5,4,3,8};//int a[] ={1,1};//int a[] ={1};//int a[] ={};//int a[] =null;int start=0;int end= a==null? -1:a.length...
堆:堆是具有特殊性质的二叉树每个结点都大于其左右儿子的的二叉树叫大顶堆每个结点都小于其左右儿子的二叉树叫做小顶堆堆排序图解: 给定一个整形数组a[]={16,7,3,20,17,8},对其进行堆排序。 首先根据该数组元素构建一个完全二叉树,得到 然后需要构造初始堆,则从最后一个非叶节点开始调整,调整过程如下:20和16交换后导致16不满足堆的性质,因此需重新调整这样就得到了初始堆。即每次调整都是从父节点、左孩子节点、右孩...
#ifndef HEAP_H #define HEAP_H #include <iostream> #include <vector> usingnamespace std;template <typename T> class Heap { public:Heap(vector<T> &_vec) : vec(_vec){}~Heap(){vec.~vector();}Heap(const Heap& rhs){this->vec = rhs.vec;}Heap &operator =(const Heap&rhs){if(this == &rhs) return *this;vec.clear();this->vec = rhs.vec;return *this;}void heapify(bool isMax,int index,int size){int l = left(inde...
插入排序就简单了,类似于打扑克,我们搬到的牌会把它插入到之前已经拍好序的牌堆中,过程如下:代码直接上:void insertSort(int a[],int length){for(int j = 1;j <= length-1;++j){int key = a[j];int i = j - 1;while(i >= 0 && a[i] > key){a[i+1] = a[i];--i;}a[i+1] =key;} }插入排序最佳情况是数组已经排好序啦;最坏情况当然是数组逆序了。最坏情况下插入排序的代价是O(n^2)。原文:http://blog.csdn.net/yu_sun90/articl...
最差时间复杂度 n*(n-1)/2,挺快的void cal(int num[],int n){ int i,j; for(i=1;i<n;i++) { int key=num[i]; j=i-1; while(j>=0&&num[j]>key) { num[j+1]=num[j--]; } num[j+1]=key; }}原文:http://www.cnblogs.com/jihe/p/4836956.html
归并排序完全遵循分治模式,主要操作分为三步:1.分解:分解待排序的n个元素序列为2个n/2个元素的子序列。2.解决:使用归并排序递归的排序两个子序列。3.合并:合并两个已排序的子序列。最重要的步骤就是合并2个已经排序的序列。例如:A和B都是从小到大排序的序列。依次对比A的第一个元素和B的第一个元素,把其中较小的元素出序列,插入到C中,直到两个序列中的元素都为空。最后,C序列就是一个包含A序列和B序列且从小到排序的序列...
以下是自己写的堆排序源码,已经测试通过,以后有时间总结,#include<stdio.h> //堆a,存储在数组a[len]中,根节点下标为i,len为数组长度 //该函数的作用是保持最大堆的性质 void Keep(int *a,int len,int i); void Build(int* a,int len); void Sort(int* a,int len); void Keep(int *a,int len,int i) {int left=2*i+1;int right=2*i+2;int largest=i,temp;if(left<len&&a[left]>a[i])largest=left;if(right<len&&a[right]>a[l...
常见排序算法总结(一)排序就是将一组对象按照某种逻辑顺序重新排列的过程本篇文章的程序代码基本结构如下:import java.util.Scanner;public class Example {public static void sort(int[] a) {//TODO//编写排序算法}private static boolean less(int v, int w) {return v < w;}private static void exch(int[] a, int i, int j) {int t = a[i];a[i] = a[j];a[j] = t;}private static boolean isSorted(int[] a) {//测试数组元素...
继上篇讲了冒泡排序的原理和代码,今天来讲一讲关于插入算法的逻辑。和冒泡排序不同,排序算法,是选择一个元素依次和位于前面的元素进行比较。比如我选择的是第i个元素,则要判断第i-1个元素的大小。 插入排序也分成两套循环,外套循环比如是指针,来选择从第几个元素开始比较,而内套循环则要开始比较选择元素和前面元素的大小,进行排序。代码如下:package cn.tgb.sort;import java.util.Arrays;//插入排序 public clas...
一.堆的介绍 动态效果图 堆有如下特点的二叉树: 1.他是完全的二叉树。也就是说,除了树的最后一层布需要时满的,其他的每一层从左到右都是满的.(如下图的完全二叉树跟不完全二叉树) 2.它常常用一个数组在实现。(如下图显示了堆它与数组之间的关系。堆在存储器中的表示是数组;堆只是概念上的表示。注意树是完全二叉树,并且所有的节点满足堆的条件) ...
二叉堆的概念二叉堆,BinaryHeap,是二叉树中的常见的一种结构。通常以最大堆和最小堆的形式呈现。最大堆指的是父节点大于等于孩子节点的value值,也就是说对于最大堆而言,根元素是二叉堆最大的元素。最小堆的概念是与最大堆的概念是相似的。下图是最大堆的示意图:二叉堆和排序之间的联系二叉堆最显著的特征就是根元素是二叉树元素间最大的或者最小的。因此每次将二叉树最大或者最小的元素取出来,同时保证每次进行这样的操作后,...
以前自己博客里留了一些java代码实现的排序算法代码,很丑陋,现在看不惯了,刚好最近买了一本《算法 第4版》。索性就一边看看这本书,一边改过去代码,顺便练习C++、python。 所以说,醉翁之意不在酒,《算法》里那些排序算法有什么意思?都是前人留下的东西,后者(现在那些大学生)学这些算法就像古代读书人读四书五经一样。所以我看重的真不是这些个算法。我看重的是编程的练习。 练习什么? 1,练习编程...