快速排序进阶

三月不练手生。翻出了以前写的快速排序、单链表快排和scala快排。老老实实写把基础版写对就足够。
本文代码均经过测试。

1,快速排序的C++写法:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getPartition(int arr[], int low, int high)
{
	int key = arr[low];
	while(low < high)
	{
		while(low < high && key <= arr[high])
			--high;
		std::swap(arr[low], arr[high]);
		while(low < high && key >= arr[low])
			++low;
		std::swap(arr[low], arr[high]);
	}

	return low;
}

void quickSort(int buf[], int low, int high)
{
	if(low < high)
	{
		int key = getPartition(buf, low, high);
		quickSort(buf, low, key-1);
		quickSort(buf, key+1, high);
	}
}

这是一个常规写法。如果是C单链表,不能随机访问数组array[index],怎么快排?

2,单链表快排 如下:

//单链表快速排序
typedef struct link_node
{
    int data;
    struct link_node* next;
}Node;

void swap(Node* a, Node*b)
{
  if(a->data == b->data) return;
  int t = a->data;
  a->data = b->data;
  b->data = t;
}

Node* getPart(Node* begin, Node* end)
{
  if(!begin) return NULL;
  int data = begin->data;
  Node* p = begin;
  Node* q = p->next;
  while(q != end)
  {
    if(q->data < data)
    {
      p = p->next;
      swap(p, q);
    }
    q = q->next;
  }
  swap(p, begin);
  return p;
}

void QuickSort(Node* begin, Node* end)
{
  if(begin != end)
  {
    Node* partition = getPart(begin, end);
    QuickSort(begin, partition);
    QuickSort(partition->next, end);
  }
}

纯C的测试程序如下:

#include <stdio.h>
#include <stdlib.h>
// 这里include quik_sort()头文件

//insert by head 头插法创建链表。
Node* create_list(int size)
{
	Node* head;
	head = NULL;
	while(size--)
	{
	  Node *t = (Node*)malloc(sizeof(Node));
	  t->data = rand()%100;
	  t->next = head;
	  head = t;
	}
	return head;
}

void show_list(Node* head)
{
  Node* p=head;
  while(p)
  {
    printf("%2d", p->data);
    p = p->next;
    if(p) printf("->");
  }
  printf("\n");
}

void del_list(Node* head)
{
  Node* p = head;
  while(p)
  {
    head = p->next;
    free(p);
    p = head;
  }
}

int main(int argc, char* argv[])
{
  Node* link = create_list(10);
  if(!link) {
    exit(0);
  }
  show_list(link);

  //Node* p = getPart(link, NULL);
  //printf("get %d\n", p->data);

  QuickSort(link, NULL);
  show_list(link);
  del_list(link);

  return 0;
}

3,scala实现快排 如下:

  // 看起来简洁,测试时并不快。
  def quickSort1(sortList:Array[Int]):Array[Int] = {
    if(sortList.length <= 1) sortList
    else{
      val pivot = sortList(sortList.length / 2)
      Array.concat(
        quickSort1(sortList.filter(pivot > _)),
        sortList.filter(pivot ==),
        quickSort1(sortList.filter(pivot < _))
      )
    }
  }
  // 正确的写法:
  def quickSort2(arr: Array[Int]): Array[Int] = {
    def qsort(left: Int, right: Int) {
      if (left < right) {
        var m = left
        for (i <- left+1 to right) {
          if (arr(i) < arr(left)) {
            m += 1
            swapArr(arr, i, m)
          }
        }
        swapArr(arr, left, m)
        qsort(left, m-1)
        qsort(m+1, right)
      }
    }
    qsort(0, arr.length - 1)
    arr
  }

  def swapArr(arr:Array[Int], a:Int, b:Int) = {
    val temp = arr(a)
    arr(a) = arr(b)
    arr(b) = temp
  }

热门文章

暂无图片
编程学习 ·

由Spring管理的对象的生命周期

注:完整代码在文章最后 生命周期:某个对象从创建到最终销毁会经历的历程! 通常,需要讨论生命周期时,对应的数据类型的对象都不是由开发人员自行维护的! 被容器维护的对象,都是由容器创建对象,并在适当的时候调用其中的某些方法的!而开发人员需要做的就是“确定满足某条…
暂无图片
编程学习 ·

用类来模拟(栈)操作

用类来模拟(栈)操作 #include <cstdio> #include <iostream> #include <cmath> #include <cstring>using namespace std;template<typename T>class Stack { public:Stack(int size =10){MAX_SIZE =10;tp =new T[size];this->size =0;}~Sta…
暂无图片
编程学习 ·

Spring-@Order注解

一、@Order 注解@Order的作用是定义Spring容器加载Bean的顺序 @Retention(RetentionPolicy.RUNTIME) @Target({ElementType.TYPE, ElementType.METHOD, ElementType.FIELD}) @Documented public @interface Order {/*** 默认最低优先级*/int value() default Ordered.LOWEST_PR…
暂无图片
编程学习 ·

常用排序:冒泡排序与快速排序详解,看完这篇就够了!风马博客

常用排序:冒泡排序与快速排序详解。在排序算法中,冒泡排序和快速排序可以算是排序算法入门必会的两种排序了,今天和大家来分析一下如何快速理解并掌握这两种排序。首先冒泡排序是初学者最常用的排序,所以我们先来详解下冒泡排序。1.冒泡排序冒泡排序,看字面意义就是有大泡泡…
暂无图片
编程学习 ·

直播带货系统开发机遇与挑战并存

如今,直播带货正逐渐取代以往传统的营销方式,各大电商也因此纷纷踏入直播带货系统开发热门,开发出多个功能为一体的直播带货系统。2020年,面临着直播带货的空前盛况,不仅是直播带货系统开发的机遇,同时也是一个挑战。所谓的直播带货,顾名思义,就是商家以及直播通过直播…
暂无图片
编程学习 ·

IntelliJ IDEA中使用markdown画流程图

安装 Scene Builder下载安装:https://gluonhq.com/products/scene-builder/ 中 Download Scene Builder for Java 8IntelliJ IDEA -> Preferences -> Languages and Frameworks -> JavaFX 中的 "Path to SceneBuilder" 设置为 "/Applications/SceneBu…
暂无图片
编程学习 ·

设计模式-建造者模式

设计模式-建造者模式 1.问题提出 盖房项目需求需要建房子:这一过程为打桩、砌墙、封顶 房子有各种各样的,比如普通房,高楼,别墅,各种房子的过程虽然一样,但是要求不要相同的. 请编写程序,完成需求.2.传统方式解决 package builder.traditional;public abstract class Ab…
暂无图片
编程学习 ·

使用ftrace分析函数性能

0. 背景 ftrace的功能非常强大,可以在系统的各个关键点上采集数据用以追踪系统的运行情况。既支持预设的静态插桩点(trace event),也支持每个函数的动态插桩(function tracer)。还可以利用动态插桩来测量函数的执行时间(function graph tracer)。关于ftrace的详细操作和原理分…
暂无图片
编程学习 ·

笔记:R输入文件数据处理txt, csv,画饼图

R输入文件数据处理txt, csv, xlsx 数据处理 1)获取文件类型 parts = strsplit(infile, split=".", fixed = TRUE) ftype = parts[[1]][length(parts[[1]])]2)根据文件类型选择输入方式 if (ftype == "csv"){loandata<<-data.frame(read.csv(infile…
暂无图片
编程学习 ·

C#中String字符串去空格的问题

1.Trim() 最常见的就是trim,trim是清除字符串前,后的空格. " A BC “被TRIM之后是"A BC” 2.LTrim(),RTrim() 分别是清除字符串前面的空格,和清除字符串后面的空格. L = Left左边 R = Right右边 3.replace() s=s.replace(" “,”") 第三种方…
暂无图片
编程学习 ·

crontab(定时启动)

crontab:定时任务的守护进程,精确到分,设计秒的我们一般写脚本 -->相当于闹钟日志文件: ll /var/log/cron*编辑文件: vim /etc/crontab 进程:ps -ef | grep crond ==> /etc/init.d/crond restart作用:定时备份,实时备份常见命令参数:usage: crontab [-…
暂无图片
编程学习 ·

【牛客网】写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

题目 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。 需要掌握 1、异或运算 两个数不相同,结果为1。两个数相同,结果为0。 2、与运算 两位同时为“1”,结果才为“1”,否则为0 3、左移 将一个二进制操作数对象按指定的移动位数向左移,左边溢…
暂无图片
编程学习 ·

[TypeScript] - TypeScript官方文档学习笔记-接口-上(二)

前言 接口只是在语法层面限制写法,从而使部分语句写法不出现,本质是语法规范 接口 TypeScript中接口用来定义结构类型,出于类型检查需要 编译转换后接口消失,仅用于语法检查 普通对象传入: function printLabel(labeledObj: { label: string }) {console.log(labeledObj.l…
暂无图片
编程学习 ·

imx6 DDR Stress Test Tool

DDR Stress Test Tool 提供了两种用途。首先,它可以用来对校准DDR3,以便于MMDC PHY delay settings和PCB配对 来达到最佳的DRAM新能。整个过程是全自动的,因此客户可以在较短的时间内让他们的DDR3工作起来。另外,该工具可以运行内存压力测试,用来验证DDR3的功能和可靠性。…
暂无图片
编程学习 ·

Java数据结构--顺序栈

一、简介 1.1 概念栈:又称为堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行插入、查找、删除等操作。 表中进行插入、删除操作的一端称为栈顶、栈顶保存的元素称为栈顶元素。相对的,表的另一端称为栈底…
暂无图片
编程学习 ·

Volatile关键字

volatile关键字 volatile 关键字是java提供的一种轻量级同步机制。他能够保证可见性和有序性,但是不能保证原子性。 volatile可见性 可见性表示被这个关键字所修饰的实例,在被修改后,其他的线程均可见。```javaclass MyData { // 如果没有volatile关键字的话,那我们在修…
暂无图片
编程学习 ·

mysql服务无法启动,报服务正在启动或停止中,请稍后片刻再试一次

这个错误我尝试了网上好多得方法最后只能卸载重装是最简单得。 于是我后面就是卸载重装了。后面就不上图了。希望有朋友碰到这个问题能给我一个解决方法。 在这里特此说明,我写得所有博客都是小编自己实际操作得。碰到得问题记录和写下解决方法得。小编也验证了很多网上别人得…
暂无图片
编程学习 ·

as 找不到调试设备(手机,虚拟机)

在flutter sdk 路径下执行命令flutter config --android-sdk D:\envi\android\android-sdk(你的android sdk路径)我在git bash 中执行之后没反应,应该是git bash环境语法设置有问题,于是改成 flutter config --android-sdk D:\\envi\\android\\android-sdk可以鸟