int algorithm(){
int array[] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63};
int count = sizeof(array)/sizeof(int);
for (int i = 0; i < count - 1; i ++) {
for (int j = 0; j < count - 1 - i; j ++) {
if (array[j] < array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
for (int index = 0; index < count; index ++) {
printf("%d", array[index]);
}
return 0;
}
func testBubbling() {
//冒泡排序
var dataArray = [24, 17, 85, 13, 9, 54, 76, 45, 5, 63]
let count = dataArray.count
for i in 0..<count-1 {
for j in 0..<count-1-i {
print("i:\(i) j:\(j)")
if dataArray[j] < dataArray[j+1] {
let temp = dataArray[j]
dataArray[j] = dataArray[j+1]
dataArray[j+1] = temp
}
}
}
for index in 0..<count {
print("result:\(dataArray[index])")
}
}
- (NSArray *)bubbleAlforithm:(NSArray *)array{
NSMutableArray *dataArray = [NSMutableArray arrayWithArray:array];
NSInteger count = dataArray.count;
for (int i = 0; i < count - 1; i ++) {
for (int j = 0; j < count - 1 - i; j ++) {
if (dataArray[j] < dataArray[j + 1]) {
id temp = dataArray[j];
[dataArray replaceObjectAtIndex:j withObject:dataArray[j+1]];
[dataArray replaceObjectAtIndex:j+1 withObject:temp];
}
}
}
return dataArray;
}
5
会和3
的位置互换,从而破坏该算法的稳定性)void selectAlgorithm(int array[]){
int count = sizeof(array)/sizeof(int);
int index;
for (int i = 0; i < count - 1; i ++) {
index = i;
for (int j = i + 1; j < count; j ++) {
if (array[index] > array[j]) {
index = j;
}
}
if (index != i) {
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
}
func selectorMethods(array: [Int]) -> [Int] {
var dataArray = array
let count = dataArray.count
var index: Int
for i in 0..<count-1 {
index = i
for j in i+1..<count {
if dataArray[index] > dataArray[j] {
index = j
}
}
if index != i {
let temp = dataArray[i]
dataArray[i] = dataArray[index]
dataArray[index] = temp
}
}
return dataArray
}
- (NSArray *)selectAlgorithm:(NSArray *)array{
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
NSInteger count = tempArray.count;
int index;
for (int i = 0; i < count - 1; i ++) {
index = i;
for (int j = i + 1; j < count; j ++) {
if (tempArray[index] > tempArray[j]) {
index = j;
}
}
if (index != i) {
id temp = tempArray[i];
[tempArray replaceObjectAtIndex:i withObject:tempArray[index]];
[tempArray replaceObjectAtIndex:index withObject:temp];
}
}
return tempArray;
}
void algorithm(int *array, int left, int right){
if (left >= right) {/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
return ;
}
int i = left;
int j = right;
int key = array[left];
while (i < j) { /*控制在当组内寻找一遍*/
while (i < j && array[j] >= key) {/*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升
序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/
j --;
}
array[i] = array[j];/*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是
a[left],那么就是给key)*/
while (i < j && array[i] <= key) {/*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
i ++;
}
array[j] = array[i];
}
array[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
//递归
algorithm(array, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
algorithm(array, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/
}
func fastAlgorithm(array:[Int], left:Int, right:Int) ->Void{
if left >= right{
return
}
var tempArray = array
var i = left
var j = right
let key = tempArray[left]
while(i < j){
while(i < j && tempArray[j] >= key){
j--
}
tempArray[i] = tempArray[j]
while(i < j && tempArray[i] <= key){
i++
}
tempArray[j] = tempArray[i]
}
tempArray[i] = key
fastAlgorithm(tempArray, left: left, right: i - 1)
fastAlgorithm(tempArray, left: i + 1, right: right)
}
- (void )fast:(NSArray *)array left:(int)left right:(int)right{
if (left >= right) {
return ;
}
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
int i = left;
int j = right;
int key = [tempArray[left] intValue];
while (i < j) {
while (i < j && [tempArray[j] intValue] >= key) {
j --;
}
tempArray[i] = tempArray[j];
while (i < j && [tempArray[i] intValue] <= key) {
i ++;
}
tempArray[j] = tempArray[i];
}
tempArray[i] = [NSNumber numberWithInt:key];
[self fast:tempArray left:left right:i - 1];
[self fast:tempArray left:i + 1 right:right];
}
void Merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex){
int i = startIndex;
int j = midIndex + 1;
int k = startIndex;
while (i != midIndex && j != endIndex) {
if (sourceArr[i] > sourceArr[j]) {
tempArr[k++] = sourceArr[j ++];
}else{
tempArr[k++] = sourceArr[i ++];
}
}
while (i != midIndex + 1) {
tempArr[k++] = sourceArr[i++];
}
while (j != endIndex + 1) {
tempArr[k ++] = sourceArr[j++];
}
for (i = startIndex; i < endIndex; i ++) {
sourceArr[i] = tempArr[i];
}
}
//recursion operation
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){
int midIndex;
if (startIndex < endIndex) {
midIndex = (startIndex + endIndex)/2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex + 1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
- (NSArray *)mergeWithArray:(NSArray *)sourceArray
startIndex:(NSInteger)startIndex
midIndex:(NSInteger)midIndex
endIndex:(NSInteger)endIndex{
NSMutableArray *sourceMutableArray = [NSMutableArray arrayWithArray:sourceArray];
NSMutableArray *tempMutableArray = [[NSMutableArray alloc] init];
NSInteger i = startIndex;
NSInteger j = midIndex + 1;
NSInteger k = startIndex;
while (i != midIndex && j != endIndex){
if (sourceMutableArray[i] > sourceMutableArray[j]) {
//tempMutableArray[k] = sourceMutableArray[j];
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
k ++;
j ++;
}else{
//tempMutableArray[k] = sourceMutableArray[i];
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
k ++;
i ++;
}
}
while (i != midIndex + 1) {
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[i]];
k ++;
i ++;
}
while (j != endIndex + 1) {
[tempMutableArray replaceObjectAtIndex:k withObject:sourceMutableArray[j]];
k ++;
j ++;
}
for (i = startIndex; i < endIndex; i ++) {
[sourceMutableArray replaceObjectAtIndex:i withObject:tempMutableArray[i]];
}
return sourceMutableArray;
}
- (NSArray *)mergeSortWithArray:(NSArray *)sourceArray
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex{
if (startIndex < endIndex) {
NSInteger midIndex = (startIndex + endIndex)/2;
NSArray *tempArray = [self mergeSortWithArray:sourceArray
startIndex:startIndex
endIndex:endIndex];
NSArray *tempArray2 = [self mergeSortWithArray:tempArray
startIndex:midIndex + 1
endIndex:endIndex];
return [self mergeWithArray:tempArray2
startIndex:startIndex
midIndex:midIndex
endIndex:endIndex];
}
return nil;
}
func mergeSort(array: [Int])-> [Int]{
var helper = Array(count: array.count, repeatedValue: 0)
var array = array
mergeSort(&array, helper: &helper, low: 0, high: array.count - 1)
return array
}
func mergeSort(inout array: [Int], inout helper:[Int], low: Int, high: Int){
guard low < high else{
return
}
let middle = (high + low)/2 + low
mergeSort(&array, helper: &helper, low: low, high: middle)
mergeSort(&array, helper: &helper, low: middle + 1, high: high)
merge(&array, helper: &helper, low: low, middle: middle, high: high)
}
func merge(inout array: [Int], inout helper: [Int], low: Int, middle:Int, high:Int){
for i in low...high{
helper[i] = array[i]
}
var helperLeft = low
var helpeRight = middle + 1
var current = low
while helperLeft <= middle && helpeRight <= high{
if helperLeft <= helpeRight{
array[current] = helper[helperLeft]
helperLeft++
}else{
array[current] = helper[helpeRight]
helpeRight++
}
current++
}
guard middle - helperLeft >= 0 else{
return
}
for i in 0...middle - helperLeft{
array[current+i] = helper[helperLeft + i]
}
}
算法实现(递归):
@interface TreeNode : NSObject
/**
* 左节点
*/
@property (nonatomic, strong) TreeNode *left;
/**
* 右节点
*/
@property (nonatomic, strong) TreeNode *right;
@end
@class TreeNode;
@interface InvertTreeNode : NSObject
/**
* 翻转二叉树算法
*
* @param node 二叉树
*
* @return 翻转后的二叉树
*/
- (TreeNode *)invertTree:(TreeNode *)node;
@end
@implementation TreeNode
@end
@implementation InvertTreeNode
- (TreeNode *)invertTree:(TreeNode *)node{
if (!node) {
return nil;
}
node.left = [self invertTree:node.left];
node.right = [self invertTree:node.right];
TreeNode *temp = node.left;
node.left = node.right;
node.right = temp;
return node;
}
@end
翻转二叉树(递归实现)
标题名写错;