0°

面试算法知识梳理一:排序算法

内容预览:
  • 始发于微信公众号: 程序员小乐 分享编程技能、互联网技术、生活感悟、...~
  • 点击上方 &;杨守乐&; ,选择“置顶公众号”,第一时间送达! “  一、...~
  • 本文介绍了排序算法的C++代码实现,排序算法目录如下: 插入排序 希尔排...~

始发于微信公众号: 程序员小乐

分享编程技能、互联网技术、生活感悟、打造干货分享平台,将总结的技术、心得、经验分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “杨守乐” ,选择“置顶公众号”,第一时间送达!



 一、概要


最近在看上学时候总结的一些东西,发现之前针对排序、字符串、数组、链表等,总结了一些面试时候常用的算法代码,因此打算整理一下分享给大家。

本文介绍了排序算法的C++代码实现,排序算法目录如下:

  • 插入排序

  • 希尔排序

  • 选择排序

  • 冒泡排序

  • 计数排序

  • 基数排序

  • 归并排序

  • 快速排序

  • 双向扫描的快速排序

  • 堆排序

 二、代码实现


2.1 插入排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void insertSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("NULL Pointer");
   int i,j,temp;
   for(i = 1; i < length; i++){
       temp = p[i];
       for(j = i; j >= 1 && p[j-1] > temp; j--)
           p[j] = p[j-1];
       p[j] = temp;
   }
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   insertSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果:

>> 2, 29, 30, 42, 50, 60, 

2.2 希尔排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void insertShell(int *p ,int inc, int length){
   if(p == NULL || length <= 0 || inc <= 0 || inc >= length)
       throw std::runtime_error("invaild input");
   int i,j,temp;
   for(i = inc; i < length; i++){
       temp = p[i];
       for(j = i; j >= inc && p[j-inc] > temp; j -= inc)
           p[j] = p[j-inc];
       p[j] = temp;
   }
}
void shellSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("invaild input");
   int inc = length >> 1;
   while(inc >= 1){
       insertShell(p,inc,length);
       inc >>= 1;
   }
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   shellSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果:

>> 2, 29, 30, 42, 50, 60, 

2.3 选择排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void selectSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("NULL Pointer");
   int i,j,mind,t;
   for(j = 0; j < length - 1; j++){
       mind = j;
       for(i = j+1; i < length; i++){
           if(p[i] < p[mind])
               mind = i;
       }
       if(mind != j){
           t = p[j]; p[j] = p[mind]; p[mind] = t;
       }
   }
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   selectSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果:

>> 2, 29, 30, 42, 50, 60, 

2.4 冒泡排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void bubbleSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("NULL Pointer");
   int i,j,t;
   for(j = 0; j < length - 1; j++)
       for(i = 0; i < length - j - 1; i++){
           if(p[i] > p[i+1]){
               t = p[i]; p[i] = p[i+1]; p[i+1] = t;
           }
   }
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   bubbleSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果:

>> 2, 29, 30, 42, 50, 60, 

2.5 计数排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void countSort(int *p, int length, int maxNum){
   if(p == NULL || length <= 0 )
       throw std::runtime_error("NULL Pointer");
   int *c = new int[maxNum+1];
   int *b = new int[length];
   int i;
   for(i = 0; i < maxNum+1; i++){
       c[i] = 0;
   }
   for(i = 0; i < length; i++){
       if(p[i] > maxNum)
           throw std::runtime_error("invaild input");
       c[p[i]] += 1;
   }
   for(i = 1; i < maxNum+1; i++){
       c[i] += c[i-1];
   }
   for(i = length-1; i >= 0; i--){
       if( c[p[i]] < 1 )
           throw std::runtime_error("error");
       b[--c[p[i]]] = p[i];
   }
   for(i = 0; i < length; i++)
       p[i] = b[i];
   delete [] c; c = NULL;
   delete [] b; b = NULL;
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   countSort(a, 6, 60);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

2.6 基数排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
int getdigit(int x, int d){
   int a[] = {1, 10, 100};
   return (x/a[d]) % 10;
}
void radixSort(int *p, int length, int d, int radix){
   if(p == NULL || length <= 0 || d <= 0)
       throw std::runtime_error("NULL Pointer");
   int i;
   int *c = new int[radix+1];
   int *b = new int[length];
   for(int j = 0; j != d; j++){
       for(i = 0; i < radix + 1; i++)
           c[i] = 0;
       for(i = 0; i < length; i++){
           int r = getdigit(p[i], j);
           if(r > radix)
               throw std::runtime_error("invaild input");
           c[r] += 1;
       }
       for(i = 1; i < radix + 1; i++)
           c[i] += c[i-1];
       for(i = length - 1; i >= 0; i--){
           int r = getdigit(p[i], j);
           if(c[r] < 1)
               throw std::runtime_error("error");
           b[--c[r]] = p[i];
       }
       for(i = 0; i < length; i++)
           p[i] = b[i];
   }
   delete [] c; c = NULL;
   delete [] b; b = NULL;
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   radixSort(a, 6, 2, 9);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

2.7 归并排序

#include <iostream>
#include <stdexcept>
using namespace std;
int INF = 0x7fffffff;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void mergeCore(int *p1, int *p2, int p1Len, int p2Len){
   if(p1 == NULL || p2 == NULL || p1Len <= 0 || p2Len <= 0)
       throw std::runtime_error("error");
   int *l = new int[p1Len+1];
   int *r = new int[p2Len+1];
   int i;
   int m = 0;
   int n = 0;
   for(i = 0; i < p1Len; i++)
       l[i] = p1[i];
   l[i] = INF;
   for(i = 0; i < p2Len; i++)
       r[i] = p2[i];
   r[i] = INF;
   i = 0;
   while(i < p1Len + p2Len){
       if(r[n] < l[m]){
           p1[i++] = r[n++];
       }else{
           p1[i++] = l[m++];
       }
   }
   delete [] l; l = NULL;
   delete [] r; r = NULL;
}
void mergeSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("error");
   if(length == 1)
       return;
   int llen,rlen;
   llen = length >> 1;
   rlen = length - llen;
   mergeSort(p,llen);
   mergeSort(p+llen,rlen);
   mergeCore(p,p+llen,llen,rlen);
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   mergeSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

2.8 快速排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void quickSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("error");
   if(length == 1)
       return;
   int mid = 0;
   int t;
   for(int i = 0; i < length; i++){
       if(p[i] < p[0]){
           mid++;
           t = p[mid]; p[mid] = p[i]; p[i] = t;
       }
   }
   t = p[0]; p[0] = p[mid]; p[mid] = t;
   int rlen = length - mid - 1;
   if(mid > 0)
       quickSort(p,mid);
   if(rlen > 0)
       quickSort(p+mid+1,rlen);
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   quickSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

2.9 双向扫描的快速排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void quickSortDouble(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("error");
   if(length == 1)
       return;
   int i = 0;
   int t;
   int mid = length;
   while(true){
       do { i++; } while( i < length && p[i] < p[0]);
       do { mid--; } while( mid > 0 && p[mid] > p[0] );
       if(i > mid) break;
       t = p[i]; p[i] = p[mid]; p[mid] = t;
   }
   t = p[0]; p[0] = p[mid]; p[mid] = t;
   int rlen = length - mid - 1;
   if(mid > 0)
       quickSortDouble(p,mid);
   if(rlen > 0)
       quickSortDouble(p+mid+1,rlen);
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   quickSortDouble(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

2.10 堆排序

#include <iostream>
#include <stdexcept>
using namespace std;
void printArray(int *p, int length) {
   for (int i = 0; i < length; i++) {
       cout << p[i] << ", ";
   }
}
void maxHeapify(int *p, int di, int length){
   if(p == NULL || length <= 0 || di >= length || di < 0)
       throw std::runtime_error("error");
   int li = (di<<1)+1;
   int t = p[di];
   while(li < length){
       if(li+1 < length && p[li+1] > p[li])
           li++;
       if(p[di] >= p[li])
           break;
       p[di] = p[li];
       di = li;
       li = (di<<1)+1;
   }
   p[di] = t;
}
void buildMaxHeap(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("error");
   for(int i=(length>>1)-1; i >= 0; i--){
       maxHeapify(p,i,length);
   }
}
void heapSort(int *p, int length){
   if(p == NULL || length <= 0)
       throw std::runtime_error("error");
   int t;
   for(int i=length; i > 0; i--){
       buildMaxHeap(p,i);
       t = p[i-1]; p[i-1] = p[0]; p[0] = t;
   }
}
int main()
{  
   int a[] = {30, 29, 50, 2, 42, 60};
   heapSort(a, 6);
   printArray(a, 6);
   return 0;
}

运行结果为:

>> 2, 29, 30, 42, 50, 60, 

如果您觉得不错,请别忘了转发、分享、点赞让更多的人去学习, 您的举手之劳,就是对小乐最好的支持,非常感谢!

如何您想进技术群和大牛们交流,关注公众号在后台回复 “加群”,或者 “学习” 即可

来自:泽毛

链接:https://www.jianshu.com/p/8d57665abde0

著作权归作者所有。本文已获得授权。欢迎投稿。

每日英文

Life’s too short to worry about what people may think or talk about you, do what you want to do and be happy. 

人生苦短,无谓去担心别人怎么想你,怎么说你,做你自己想做的,快乐一点。

乐乐有话说

人生的滋味,哪怕是酸甜或苦辣,也要靠自己去品。凡事都要留有余地,势不可用尽,幸福是一种感觉,它只能源于自己内心的感觉,而并不取决于物质的多寡,很多时候,物质的锈蚀反倒让人失去了体检幸福的触觉。

面试算法知识梳理一:排序算法


推荐阅读







看完本文有收获?请转发分享给更多人
关注「杨守乐」,提升技能

以上就是:面试算法知识梳理一:排序算法 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论