算法的C++实现"/>
常见排序算法的C++实现
常见排序算法c++实现
文章目录
- 常见排序算法c++实现
- 前言
- 一、冒泡排序
- 二、选择排序
- 三、插入排序
- 四、希尔排序
- 五、快速排序
- 六、归并排序
前言
应为快毕业了,想回顾一下数据结构和算法 @_@
所以花了一点时间把排序算法实现了一下。(至于各个算法之间的比较啊,优缺点啊,什么时间复杂度,空间复杂度啊,本文没有)
提示:以下是本篇文章正文内容,下面案例可供参考,我们从简单的开始
一、冒泡排序
冒泡简单的说就是两两比较,最直接也是最简单的
void bubbleSort(int * arr, int size)
{int time=size;for (int j = 0; time>1; j++){for (int i = 0; i < time-1; i++){if (arr[i] > arr[i+1]){int temp = arr[i];arr[i] = arr[i+1];arr[i+1] = temp;}}time--;}
}
二、选择排序
正如他的名字,每遍历一次挑选出最大(最小)的放到队列里
代码如下(示例):
void selectSort(int * arr, int size)
{for (int i = size-1; i > 0; i--){int max = i;for (int j = 0; j < i; j++){if (arr[j] > arr[max]){int temp = arr[j];arr[j] = arr[max];arr[max] = temp;}}}
}
三、插入排序
就像我们抓牌一样,抓一张插到对应的位置
void insertSort(int * arr, int size)
{for (int i = 1; i < size; i++){int j = i - 1;int temp = arr[i];while (arr[j] > temp && j >= 0){arr[j+1] = arr[j];j--;}arr[j+1] = temp;}//这个就不那么好了/*for (int i = 0; i < size; i++){for (int j = i+1; j < size; j++){for (int k = 0; k <= i; k++){if (arr[j] < arr[k]){int temp = arr[j];arr[j] = arr[k];arr[k] = temp;}}}}*/
}
四、希尔排序
对插入排序的升级,比插入排序更快
void shellSort(int * intArr, int size)
{int step = size / 2; //原始步长int nTemp = 0;while (step > 0){for (int i = step; i < size; i++){nTemp = intArr[i];int j = i - step;while (j >= 0 && intArr[j] > nTemp){intArr[j + step] = intArr[j];j = j - step;}intArr[j + step] = nTemp;}step /= 2;} /*int step = size / 2;while(step > 0){for (int j = 0; j < size; j++){for (int i = j; i < size; i += step){int k = i - step;int temp = arr[i];while (arr[k] > temp&&k >= 0){arr[k + step] = arr[k];k -= step;}arr[k + step] = temp;}}step = step / 2;}*/
}
五、快速排序
递归版,可能有BUG哈
void quick(int * arr, int left, int right)
{int key = arr[left];int l = left, r = right;while (l < r){while (l < r && arr[r] >= key){r--;}while (l < r && arr[l] < key){l++;}if (l < r){swap(&arr[l], &arr[r]);}}if (left < right){quick(arr, left, l);quick(arr, l+1, right);}
}void swap(int * a, int * b)
{int temp = *a;*a = *b;*b = temp;
}void quickSort(int * arr, int size)
{quick(arr,0,size-1);
}
六、归并排序
void mergeSort(int * arr, int size)
{int*arr1 = 0;int*arr2 = 0;if (size > 1){arr1 = new int[size / 2];arr2 = new int[size - size / 2];memcpy(arr1, arr, size / 2 * sizeof(int));memcpy(arr2, arr + size / 2, (size - size / 2) * sizeof(int));mergeSort(arr1, size / 2);mergeSort(arr2, size - size / 2);}if (size == 1)return;int i = 0;int j = 0;int k = 0;while (i < size / 2 && j < size - size / 2){arr[k++] = arr2[j] < arr1[i] ? arr2[j++] : arr1[i++];}//arr[k] = arr2[j] < arr1[i] ? arr2[j++] : arr1[i++];if (i > size / 2 - 1 && j< size - size / 2){memcpy(&arr[k], &arr2[j], sizeof(int)*(size - size / 2 - j));}if (j > size - size / 2 - 1&& i < size / 2){memcpy(&arr[k], &arr1[i], sizeof(int)*(size / 2 - i));}
}
更多推荐
常见排序算法的C++实现
发布评论